int len = words.length; boolean[][] cnt = newboolean[len][26]; for (int i = 0; i < len; i++) { String word = words[i]; for (char ch : word.toCharArray()) { cnt[i][ch - 'a'] = true; } }
int ans = 0; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { boolean flag = true; for (int k = 0; k < 26; k++) { if (cnt[i][k] && cnt[j][k]) { flag = false; break; } }
if (flag) { ans = Math.max(ans, words[i].length() * words[j].length()); } } }
return ans; }
复杂度分析:
时间复杂度:O(L+n2×26),其中其中 L 是数组 words 中的全部单词长度之和, n 是数组 words 的长度。
int len = words.length; int[] masks = newint[len]; for (int i = 0; i < len; i++) { String word = words[i]; int wordLen = word.length(); for (int j = 0; j < wordLen; j++) { masks[i] |= 1 << (word.charAt(j) - 'a'); } }
int ans = 0; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { if ((masks[i] & masks[j]) == 0) { ans = Math.max(ans, words[i].length() * words[j].length()); } } }
return ans; }
复杂度分析:
时间复杂度:O(L+n2)。其中 L 是数组 words 中的全部单词长度之和,n 是数组 words 的长度。预处理每个单词的位掩码需要遍历全部单词的全部字母,时间复杂度是 O(L),然后需要使用两重循环遍历位掩码数组 masks计算最大单词长度乘积,时间复杂度是 O(n2),因此总时间复杂度是 O(L+n2)。
空间复杂度:O(n)。需要创建长度为 n 的位掩码数组 masks。
方法三:位运算优化
方法二需要对数组 words 中的每个单词计算位掩码,如果数组 words 中存在由相同的字母组成的不同单词,则会造成不必要的重复计算。例如单词 meet 和 met 包含的字母相同,只是字母的出现次数和单词长度不同,因此这两个单词的位掩码表示也相同。
int len = words.length; Map<Integer, Integer> maskMap = new HashMap<>(); for (int i = 0; i < len; i++) { String word = words[i]; int wordLen = word.length(); int mask = 0; for (int j = 0; j < wordLen; j++) { mask |= 1 << (word.charAt(j) - 'a'); } if (wordLen > maskMap.getOrDefault(mask, 0)) { maskMap.put(mask, wordLen); } }
int ans = 0; Set<Integer> maskSet = maskMap.keySet(); for (int mask1 : maskSet) { int len1 = maskMap.get(mask1); for (int mask2 : maskSet) { if ((mask1 & mask2) == 0) { int len2 = maskMap.get(mask2); ans = Math.max(ans, len1 * len2); } } }
return ans; }
复杂度分析:
时间复杂度:O(L+n2),其中L是数组 words 中的全部单词长度之和,n是数组 words 的长度。预处理每个单词的位掩码并将位掩码对应的最大单词长度存入哈希表需要遍历全部单词的全部字母,时间复杂度是 O(L),然后需要使用两重循环遍历哈希表计算最大单词长度乘积,时间复杂度是 O(n2),因此总时间复杂度是 O(L+n2)。
空间复杂度:O(n),其中 n 是数组 words 的长度。需要创建哈希表记录每个位掩码对应的最大单词长度,哈希表中的记录数量不会超过 n。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)