318. 最大单词长度乘积
难度中等
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"] 输出: 16 解释: 这两个单词为 "abcw", "xtfn"。
示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 解释: 这两个单词为 "ab", "cd"。
示例 3:
输入: ["a","aa","aaa","aaaa"] 输出: 0 解释: 不存在这样的两个单词。
提示：
- 2 <= words.length <= 1000
- 1 <= words[i].length <= 1000
- words[i] 仅包含小写字母
题解
思路：遍历 每次找最长的单词，然后找到符合题意（即与它没有公共字母）的另外一个单词，计算length(word[i]) * length(word[j]) ，并和记录的最大比较 就找下一个最长的单词，然后找到它所对应的符合题意的另外一个单词，计算length(word[i]) * length(word[j]) ，并和记录的最大比较 依次，知道完为止 可以先对字符串数组从长到短排个序
class Solution { public int maxProduct(String[] words) { Arrays.sort(words,new Comparator<String>() { @Override public int compare(String o1, String o2) { return -(o1.length()-o2.length()); } }); int maxProduct=0; // System.out.println(Arrays.toString(words)); for (int i=0;i<words.length;i++){ for (int j = i+1; j <words.length; j++) { HashSet<Character> set=new HashSet<>(); int m=words[i].length(); int n=words[j].length(); //有公共字母==两个的并集大小<两个大小之和 //没有的话是等于 for (int k = 0; k < m; k++) { set.add(words[i].charAt(k)); } for (int k = 0; k < n; k++) { set.add(words[j].charAt(k)); } // System.out.println(set); if (set.size()==m+n){ if(m*n>maxProduct){ maxProduct=m*n; } } } } return maxProduct; } }
错误原因没有考虑到单词本身会有重复字母
排序没作用
class Solution { public int maxProduct(String[] words) { int maxProduct=0; // System.out.println(Arrays.toString(words)); for (int i=0;i<words.length;i++){ for (int j = i+1; j <words.length; j++) { boolean notHasCommonChar=true; int m=words[i].length(); int n=words[j].length(); for (int k = 0; k <m; k++) { char ch=words[i].charAt(k); int index = words[j].indexOf(ch); if (index!=-1){ notHasCommonChar=false; break; } } if (notHasCommonChar){ if(m*n>maxProduct){ maxProduct=m*n; } } } } return maxProduct; } }
官方
方法一：位运算
如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)，则可以将总时间复杂度降低到 O(n2)
)。可以使用位运算预处理每个单词，通过位运算操作判断两个单词是否有公共字母。由于单词只包含小写字母，共有 26 个小写字母，因此可以使用位掩码的最低 26 位分别表示每个字母是否在这个单词中出现。将a 到 z 分别记为第 0 个字母到第 25 个字母，则位掩码的从低到高的第 i 位是 11 当且仅当第 i 个字母在这个单词中，其中 0≤i≤25。
用数组 masks 记录每个单词的位掩码表示。计算数组 masks 之后，判断第 i 个单词和第 j个单词是否有公共字母可以通过判断 masks[i] & masks[j] 是否等于 0 实现，当且仅当masks[i] & masks[j]=0 时第 i 个单词和第 j 个单词没有公共字母，此时使用这两个单词的长度乘积更新最大单词长度乘积。
class Solution { public int maxProduct(String[] words) { int length = words.length; int[] masks = new int[length]; for (int i = 0; i < length; i++) { String word = words[i]; int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { masks[i] |= 1 << (word.charAt(j) - 'a'); } } int maxProd = 0; for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if ((masks[i] & masks[j]) == 0) { maxProd = Math.max(maxProd, words[i].length() * words[j].length()); } } } return maxProd; } }
作者：LeetCode-Solution
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
时间复杂度：O(L+n2 )，其中 L 是数组words 中的全部单词长度之和，n 是数组 words 的长度。预处理每个单词的位掩码需要遍历全部单词的全部字母，时间复杂度是 O(L)，然后需要使用两重循环遍历位掩码数组masks 计算最大单词长度乘积，时间复杂度是 O(n2)，因此总时间复杂度是 O(L + n2)
空间复杂度：O(n)，其中 n 是数组 words 的长度。需要创建长度为 n 的位掩码数组 masks。
方法二：位运算优化
class Solution { public int maxProduct(String[] words) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int length = words.length; for (int i = 0; i < length; i++) { int mask = 0; String word = words[i]; int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { mask |= 1 << (word.charAt(j) - 'a'); } if (wordLength > map.getOrDefault(mask, 0)) { map.put(mask, wordLength); } } int maxProd = 0; Set<Integer> maskSet = map.keySet(); for (int mask1 : maskSet) { int wordLength1 = map.get(mask1); for (int mask2 : maskSet) { if ((mask1 & mask2) == 0) { int wordLength2 = map.get(mask2); maxProd = Math.max(maxProd, wordLength1 * wordLength2); } } } return maxProd; } }
