首页 > itarticle > maximum product of word lengths

maximum product of word lengths

admin 11月 11, 2020 0

Problem:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

分析

bit manipulation。由于只有26个字母，因此我们可以用一个26的binary string来表示当前字符串表示的binary number。那么要想判定两个字符串是否有相同字符，只要把两个binary string与上就好了。结果若为0，那么不存在相同字符，否则存在相同字符。

很好理解，但是不容易想到bit解法。

public class  {
    public int maxProduct(String[] words) {
        if (words == null || words.length == 0) return 0;
        int ret = 0;
        int length = words.length;
        int[] mask = new int[length];
        
        for (int i = 0; i < length; i++) {
            String cur = words[i];
            for (int j = 0; j < cur.length(); j++) {
                mask[i] |= 1 << (cur.charAt(j) - 'a');
            }
        }
        
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    ret = Math.max(ret, words[i].length() * words[j].length());
                }
            }
        }
        return ret;
    }
}