LCR.P5[最大单词长度乘积]

方法一：暴力

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
class Solution {
    public int maxProduct(String[] words) {
        Set<Character> set = new HashSet<>();
        int ans = 0, n = words.length;
        for (int i = 0; i < n - 1; ++i) {
            String word1 = words[i];
            for (int k = 0; k < word1.length(); ++k) {
                set.add(word1.charAt(k));
            }

            for (int j = i + 1; j < n; ++j) {
                boolean flag = true;
                String word2 = words[j];
                for (int k = 0; k < word2.length(); ++k) {
                    if (set.contains(word2.charAt(k))) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    ans = Math.max(ans, word1.length() * word2.length());
                }
            }
            set.clear();
        }
        return ans;
    }
}
  • 时间复杂度：$O(nm)$
  • 空间复杂度：$O(m)$

方法二：位运算+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxProduct(String[] words) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int mask = 0, m = word.length();
            for (int i = 0; i < m; ++i) {
                int u = word.charAt(i) - 'a';
                mask |= (1 << u);
            }
            if (!map.containsKey(mask) || map.get(mask) < m) map.put(mask, m);
        }
        for (int a : map.keySet()) {
            for (int b : map.keySet()) {
                if (((a & b) == 0)) {
                    ans = Math.max(ans, map.get(a) * map.get(b));
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(max(\sum_{i = 0}^{n - 1}words[i].length), n^2)$
  • 空间复杂度：$O(n)$