剑指 Offer II 005单词长度的最大乘积

你的名字 2024-03-27 11:24 16阅读 0赞

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

示例 1:

输入: words = \["abcw","baz","foo","bar","fxyz","abcdef"\]  
输出: 16  
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。  
示例 2:

输入: words = \["a","ab","abc","d","cd","bcd","abcd"\]  
输出: 4  
解释: 这两个单词为 "ab", "cd"。  
示例 3:

输入: words = \["a","aa","aaa","aaaa"\]  
输出: 0  
解释: 不存在这样的两个单词。

提示：

2 <= words.length <= 1000  
1 <= words\[i\].length <= 1000  
words\[i\] 仅包含小写字母

## 知识点： ##

1.indexOf () ：方法返回一个整数值，指出 某一个String 对象内子字符串的开始位置。如果没有找到子字符串，则返回-1。

2.toCharArray() ：String.toCharArray()，将字符串转化为字符数组

## 方法一：暴力解法 ##

由题我们可以很自然想到是两个for循环，一个for用来取出数组中的字符串，另一个for用来遍历字符串中的字符。而怎么比较呢？可以将字符串转化为字符数组，一个个字符取出做比较。

class Solution {
        public int maxProduct(String[] words) {
            int fin = 0 ;
            for(int i=0;i<words.length;i++){
                String word1 = words[i];
                //O(n^2)
                for(int j=i+1;j<words.length;j++){
                    String word2 = words[j];
                    if(!hasSameChar(word1,word2)){
                        fin=Math.max(fin,word1.length()*word2.length());
                    }
                }
            }
            return fin;
        }
        //O(m^2)
        public boolean hasSameChar(String word1,String word2){
            for(char c:word1.toCharArray()){
                if(word2.indexOf(c)!=-1) return true;
            }
            return false;
        }
    }

时间复杂度(n^2\*m^2）

## 方法二：计算优化 ##

hasSameChar方法里的复杂度为m^2（因为是word1里先拿出一个元素，再与word2里全部元素作比较，相当于两个for），而两个for循环是n^2，所以首先是可以从这两方面进行性能的优化。

我们可以把hasSameChar两个for拆开。我们先可以把出现的字符放到一个数组里，然后再去与另一个字符串作比较，这样我们就拆开了两个for。而因为字符里只有小写的字母，因此我们可以把出现的字符当做下标，出现了就位置上填1。

// O(m)
    private boolean hasSameChar2(String word1, String word2) {
        //26个字母
        int[] count = new int[26];
        //字母出现的位置，a作为0下标起点
        for (char c : word1.toCharArray()) count[c - 'a'] = 1;
        for (char c : word2.toCharArray()) {
            if (count[c - 'a'] == 1) return true;
        }
        return false;
    }

## 方法三：位运算 ##

既然都说到0和1了，那我们其实可以把他当做是一个26个bit位的一个运算，然后像上个方法一样出现了的数字就放1。如下图所示

![aa752db44810494a8730883c02e0f660.png][]

而下一个字母，比如g，出现了的话，要算出g的下标，其实就是将1位移a相对g的差值，然后将其并列入先前的数组，就用按位或 |（全1才为1）就可更新数组

![281afb67b567482bb5b3a1081e7d9813.png][]

而数组中如果出现了相同的字符，我们可以进行按位与&（同则1，异则0），如果有相同的字符，就会出现有1.

![7e493c52672f48729d8eae42625227e0.png][]

![25498ed9e04d44f495a8a7680e5f1d64.png][]

// O(m)
    private boolean hasSameChar(String word1, String word2) {
        int bitMask1 = 0, bitMask2 = 0;
        for (char c : word1.toCharArray()) bitMask1 |= (1 << (c - 'a'));
        for (char c : word2.toCharArray()) bitMask2 |= (1 << (c - 'a'));
        return (bitMask1 & bitMask2) != 0;
    }

参考文章

[简单易懂Java/C++ /Python/js/go - 最大单词长度乘积 - 单词长度的最大乘积 - 力扣（LeetCode）][Java_C_ _Python_js_go - _ - _ - _LeetCode]

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/aseY1I  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[aa752db44810494a8730883c02e0f660.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/479ddb071c5b4d559855118fe0be3758.png
[281afb67b567482bb5b3a1081e7d9813.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b4650223ee5f4b4d936fcdf17e22ab09.png
[7e493c52672f48729d8eae42625227e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/65f6ce88499b4cb290990c7d87302e4a.png
[25498ed9e04d44f495a8a7680e5f1d64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/84e0f813e503430d8bd17331cade6527.png
[Java_C_ _Python_js_go - _ - _ - _LeetCode]: https://leetcode.cn/problems/aseY1I/solution/jian-dan-yi-dong-javac-pythonjs-zui-da-d-ffga/