LC.P318[最大单词长度乘积]

方法一：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(String[] words) {
        int n = words.length, ans = 0;
        int[] mask = new int[n];
        for (int i = 0; i < n; ++i) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
            for (int j = 0; j < i; ++j) {
                if ((mask[i] & mask[j]) == 0) {
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2+L)$，其中$L$为数组$words$中的全部单词长度之和
  • 空间复杂度：$O(n)$