My C++ solution using bit manipulation with explanation


  • 2
    B

    Firstly, I convert the string into a 32 bits integer because the string only contains 'a'-'z', i.e., the maximum number it can represent is (1<<27)-1, which is less than INT_MAX. After converting into the integer, judging whether two strings have common can achieved with bit and & because if two strings have common letter, the corresponding bit will be set 1.

    class Solution {
    public:
    int convert(string str){
        int ret = 0;
        int len = str.length();
        for(int i = 0; i < len; i ++) ret = (ret | (1<<(str[i] - 'a')));
        return ret;
    }
    
    int maxProduct(vector<string>& words) {
        vector<pair<int, int>> vec;
        int len = words.size();
        for(int i = 0; i < len; i ++){
            vec.push_back(make_pair(words[i].length(), convert(words[i])));
        }
        
        int ret = 0;
        for(int i = 0; i < len; i ++){
            for(int j = i + 1; j < len; j ++){
                if((vec[i].second & vec[j].second) != 0) continue;
                ret = max(ret, vec[i].first * vec[j].first);
            }
        }
        return ret;
    }
    };

  • -1
    H

    A word can contain more than 27 letters such as since char can be duplicated. More test cases need to be added. However, all words with length > 27 can be excluded though. So you just need a small fix in the solution.


  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • -1
    Z

    I don't agree with you, the problem is only care of whether there exists same letter, there're only 26 letters, so you just need 26 bits to record if the letter appears, unrelate with the length of the string or the duplicate.


Log in to reply
 

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