【leetcode】单词长度的最大乘积

一、 题目描述

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

二、代码思路

2.1 暴力求解

• 遍历数组，依次将words[i]的字符串与words数组的每个字符串进行比较，看是否有相同字符，无相同字符则计算两个字符串长度乘积，并与最大值比较。
• 如何判断两个字符串有相同字符呢？一样的道理，使用嵌套的两个for循环，分别比较一个字符在另一个字符串中有没有相同的。
• 这样看来，妥妥的O(N^4)复杂度，最后两个点超时。

2.2 暴力求解优化1

• 缺点1：含有重复比较：

 for(int i=0;i<words.length;i++){
            for(int j=0;j<words.length;j++){
1
2

1 2 3 4
1 2 3 4
第一轮：1跟 2 3 4比较，第二轮：2就不需要跟1 比较了，只需要跟3 4比即可。

• 缺点2：比较两个字符串是否有相同字符时，没有用到String的方法如：indexOf(String)、boolean contains(String) , 所以导致复杂度较高。

2.3 使用计数优化

• 题目中都是小写字母
• 所以我们可以有这样一种思路：将字符串的字符都映射到一个26个大小的数组中，出现一个字符则数组对应位置count+1.
• 如此，如果我们判断一个字符串是否包含另一个字符串就只需要判断对应位置的count是否为-1，也就是array(char-‘a’)-1。
• 判断一个字符串是否包含一个字符更加方便，只需要判断该字符对应数组的count是否大于0即可。
• 所以判断字符是否在一个字符串中的复杂度就降到了O(N)。

2.4 位运算优化

• 使用int[]26数组，来存放某个字符是否存在，这样有点废空间。
• 本质上存在为1，不存在为0，所以使用26的bit位即可，也就是一个int即可。
• 1<<‘char’-‘a’，就相当于在对应位置的二进位赋值1：
  1<<‘b’-‘a’ = 1<<1=0001<<1=0010
• 通过 int bitMask1, bitMask2 ;(bitMask1 & bitMask2) != 0;也就是通过&来判断是否有相同位置有相同的1。 我们知道& 同1才为1，所以只有存在二进制位同1，计算结果才不为0；也意味着有相同字符。

2.5 位运算预计算

• 既然可以用bitmask来表示对应字符串所存在的个数

2.6 再次优化

• eg eegg eeeggeeggg,这三个字符串的bitmask其实是一样的。
• 只存储字符串长度最长的bitmask。

三、代码

3.1 暴力解法：

class Solution {
    public int maxProduct(String[] words) {
        int maxLength=0;
        for(int i=0;i<words.length;i++){
            for(int j=0;j<words.length;j++){
                int flag=0;
                for(int k=0;k<words[i].length();k++){
                    for(int l=0;l<words[j].length();l++){
                        if(words[i].charAt(k)==words[j].charAt(l)){
                            flag=1;//证明有相同字符
                            break;
                        }
                    }
                    if(flag==1) break;
                }
                if(flag==0) {
                    maxLength=
                            maxLength>words[i].length()*words[j].length() ?
                            maxLength : words[i].length()*words[j].length();
                }
            }
        }
        return maxLength;
    }
}
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

时间复杂度：0(N^4) 明显超时了

3.2 暴力解法优化1：

class Solution {
    public int maxProduct(String[] words) {
        int maxLength=0;
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
               if(judgeSameString(words[i],words[j])==false){
                   maxLength=maxLength>words[i].length()*words[j].length() ? maxLength :words[i].length()*words[j].length();
               }
            }
        }
        return maxLength;
    }
    private boolean judgeSameString(String str1,String str2){
         boolean flag=false;
         for(char a : str1.toCharArray()){
             if(str2.indexOf(a)!=-1){
                 flag=true; //不等于-1证明 两个字符串有相同字符，则不用比较
                 break;
             }
         }
         return flag;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(N^2* m^2)

3.3计数优化算法：

class Solution {
    public int maxProduct(String[] words) {
        int maxLength=0;
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
               if(judgeSameString(words[i],words[j])==false){
                   maxLength=maxLength>words[i].length()*words[j].length() ? maxLength :words[i].length()*words[j].length();
               }
            }
        }
        return maxLength;
    }
    private boolean judgeSameString(String str1,String str2){
         boolean flag=false;
         int array[]=new int[26];
         for(char c: str1.toCharArray()) array[c-'a']=1;
         for(char c: str2.toCharArray()){
             if(array[c-'a']!=0){
                 flag=true;
                 break;
             }
         }
         return flag;
    }
}
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

时间复杂度：O(N^2*M)

3.4 位运算优化

class Solution {
    public int maxProduct(String[] words) {
        int maxLength=0;
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
               if(judgeSameString(words[i],words[j])==false){
                   maxLength=maxLength>words[i].length()*words[j].length() ? maxLength :words[i].length()*words[j].length();
               }
            }
        }
        return maxLength;
    }
    private boolean judgeSameString(String str1,String str2){
            int bitMask1 = 0, bitMask2 = 0;
            for (char c : str1.toCharArray()) bitMask1 |= (1 << (c - 'a'));
            for (char c : str2.toCharArray()) bitMask2 |= (1 << (c - 'a'));
            return (bitMask1 & bitMask2) != 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 5 位运算预计算

// 位运算 + 预计算
// 时间复杂度：O((m + n)* n)
// 空间复杂度：O(n)
public int maxProduct2(String[] words) {
    // O(mn)
    int n = words.length;
    int[] masks = new int[n];
    for (int i = 0; i < n; i++) {
        int bitMask = 0;
        for (char c : words[i].toCharArray()) {
            bitMask |= (1 << (c - 'a'));
        }
        masks[i] = bitMask;
    }

    // O(n^2)
    int ans = 0;
    for (int i = 0; i < words.length; i++) {
        String word1 = words[i];
        for (int j = i + 1; j < words.length; j++) {
            String word2 = words[j];
            if ((masks[i] & masks[j]) == 0) {
                ans = Math.max(ans, word1.length() * word2.length());
            }
        }
    }
    return ans;
}

作者：tangweiqun
链接：https://leetcode.cn/problems/aseY1I/solution/jian-dan-yi-dong-javac-pythonjs-zui-da-d-ffga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

3.6 位运算再次优化

// 位运算 + 预计算
// 时间复杂度：O((m + n)* n)
// 空间复杂度：O(n)
public int maxProduct(String[] words) {
    // O(mn)
    Map<Integer, Integer> map = new HashMap<>();
    int n = words.length;
    for (int i = 0; i < n; i++) {
        int bitMask = 0;
        for (char c : words[i].toCharArray()) {
            bitMask |= (1 << (c - 'a'));
        }
        // there could be different words with the same bitmask
        // ex. ab and aabb
        map.put(bitMask, Math.max(map.getOrDefault(bitMask, 0), words[i].length()));
    }

    // O(n^2)
    int ans = 0;
    for (int x : map.keySet()) {
        for (int y : map.keySet()) {
            if ((x & y) == 0) {
                ans = Math.max(ans, map.get(x) * map.get(y));
            }
        }
    }
    return ans;
}

作者：tangweiqun
链接：https://leetcode.cn/problems/aseY1I/solution/jian-dan-yi-dong-javac-pythonjs-zui-da-d-ffga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

四、参考资料

String方法