最大单词长度乘积【LC318】
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
2022/10/17
位运算
将每个单词转化为整数（二进制形式），用最低位代表a，第二低位代表b……最高位（第二十六位）代表z，例如单词“ab”可表示为11，十进制为3
将某个单词的二进制形式与其他单词进行与运算，如果结果为0，那么代表这两个单词不含有公共字母，判断是否需要更新结果
代码
class Solution { public int maxProduct(String[] words) { int len = words.length; int[] binary = new int[len]; // a:1 b:2 c:4 …… for (int i = 0; i < len; i++){ String str = words[i]; boolean[] map = new boolean[26]; for (int j = 0; j < str.length(); j++){ int n = str.charAt(j)-'a'; if (!map[n]){ binary[i] += Math.pow(2,n); map[n] = true; } } } int res = 0; for (int i = 0; i < len; i++){ for (int j = i + 1; j < len; j++){ if ((binary[i] & binary[j]) == 0){ res = Math.max(res,words[i].length()*words[j].length()); } } } return res; } }
- 复杂度
- 时间复杂度：O(n2+nk)，n为字符串的个数，k为每个字符串的平均长度
- 空间复杂度：O(n)
- 优化
将每个字符串转化为二进制的代码可优化为
for (int i = 0; i < len; i++){ String str = words[i]; for (char ch: words[i].toCharArray()){ binary[i] |= 1 << (ch - 'a'); } }
代码
class Solution { public int maxProduct(String[] words) { int len = words.length; boolean[][] flags = new boolean[len][26]; for (int i = 0; i < len; i++){ String str = words[i]; for (char ch: words[i].toCharArray()){ flags[i][ch-'a'] = true; } } int res = 0; for (int i = 0; i < len; i++){ for (int j = i + 1; j < len; j++){ int k = 0; for (; k < 26; k++){ if (flags[i][k] && flags[j][k]){ break; } } if (k == 26){ res = Math.max(res,words[i].length()*words[j].length()); } } } return res; } }
- 复杂度
- 时间复杂度：O(n2+nk)，n为字符串的个数，k为每个字符串的平均长度
- 空间复杂度：O(n)
