C++ Bit manipulation Solution beats 100%


  • 0
    Z

    Preprocessing the strings into its binary format, then using this binary representation to determine whether two words sharing same letters or not..
    Time complexity is O(m*n+ n^2), m is the max length of words, n is the length of vector

    class Solution {
    public:
        int transform(string& s) {
            int res = 0;
            for(char c : s) {
                res |= 1 << (c-'a');
            }
            return res;
        }
        int maxProduct(vector<string>& words) {
            int res = 0;
            vector<int> binary(words.size());
            for(int i = 0; i < words.size(); i++) {
                binary[i] = transform(words[i]);
            }
            
            for(int i = 0; i < binary.size(); i++) {
                for(int j = i+1; j < binary.size(); j++) {
                    if((binary[i] & binary[j]) == 0) {
                        res = max(res, (int)(words[i].size() * words[j].size()));
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.