By Long Luo
Leetcode 318. 最大单词长度乘积 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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] 仅包含小写字母
方法一:暴力 + 状态压缩
思路与算法:
之前做过类似的题目,而且题目中有明显的提示 w o r d s [ i ] words[i] w o r d s [ i ] 仅包含小写字母,那么先统计出每个单词中的字母数量。
之后两层for
遍历字符串,枚举两个字符串 w o r d s [ i ] words[i] w o r d s [ i ] 和 w o r d s [ j ] words[j] w o r d s [ j ] ,然后暴力检验 w o r d s [ i ] words[i] w o r d s [ i ] 和 w o r d s [ j ] words[j] w o r d s [ j ] 是否有公共字母,并更新最大值。
比较简单,代码如下所示:
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 29 30 31 32 33 public static int maxProduct (String[] words) { if (words == null || words.length <= 1 ) { return 0 ; } int len = words.length; boolean [][] cnt = new boolean [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 + n 2 × 26 ) O(L + n^2 \times 26) O ( L + n 2 × 2 6 ) ,其中其中 L L L 是数组 words \textit{words} words 中的全部单词长度之和, n n n 是数组 words \textit{words} words 的长度。
空间复杂度:O ( 26 × n ) O(26 \times n) O ( 2 6 × n ) ,其中 n n n 是数组 words \textit{words} words 的长度。
方法二:位运算
方法一中判断两个单词是否有公共字母需要进行 26 26 2 6 次比较,如果可以将其时间复杂度降低到 O ( 1 ) O(1) O ( 1 ) ,可以将总时间复杂度降低到 O ( n 2 ) O(n^2) O ( n 2 ) 。
可以使用位运算预处理每个单词,通过位运算操作判断两个单词是否有公共字母。
由于单词只包含小写字母,共有 26 26 2 6 个小写字母,而 i n t int i n t 有 32 32 3 2 位,因此可以使用位掩码的最低 26 26 2 6 位分别表示每个字母是否在这个单词中出现。将 a \textit{a} a 到 z \textit{z} z 分别记为第 0 0 0 个字母到第 25 25 2 5 个字母,则位掩码的从低到高的第 i i i 位是 1 1 1 当且仅当第 i i i 个字母在这个单词中,其中 0 ≤ i ≤ 25 0 \le i \le 25 0 ≤ i ≤ 2 5 。
用数组 masks \textit{masks} masks 记录每个单词的位掩码表示。计算数组 masks \textit{masks} masks 之后,判断第 i i i 个单词和第 j j j 个单词是否有公共字母可以通过判断 masks [ i ] & masks [ j ] \textit{masks}[i]~\&~\textit{masks}[j] masks [ i ] & masks [ j ] 是否等于 0 0 0 实现,当且仅当 masks [ i ] & masks [ j ] = 0 \textit{masks}[i]~\&~\textit{masks}[j] = 0 masks [ i ] & masks [ j ] = 0 时第 i i i 个单词和第 j j j 个单词没有公共字母,此时使用这两个单词的长度乘积更新最大单词长度乘积。