318. 最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

---

复杂度：O(N*N)
思路：使用位运算masks进行模拟每个字符的是否出现。两个字符串没有相同字符，那么他们的masks的&为0。

class Solution {
    public int maxProduct(String[] words) {
        /**
        位运算模拟字符
         */
        int n = words.length;
        
        // 记录每个String中具有的字符
        int[] tmp = new int[n];
        int idx = 0;
        for(String w:words) {
            int t = 0;
            for(int i=0; i<w.length(); i++) {
                int u = w.charAt(i) - 'a';
                // 记录该字符位置
                t |= (1<<u);
            }
            tmp[idx++] = t;
        }
        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if((tmp[i]&tmp[j])==0) {
                    ans = Math.max(ans, words[i].length()*words[j].length());
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30