单词长度的最大乘积

发布日期: 2023-06-10

更新日期: 2023-06-10

文章字数: 730

阅读时长: 3 分

阅读次数:

题目描述：

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

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

数据集：

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

思路分析

首先会想到的是，通过两重for循环，逐个比较两个字符串是否有相同字符，如果没有相同字符，则计算他们长度的乘积，然后与当前最大值比较，如果大于最大值，则将当前乘积结果更新为最大值。但这种算法逻辑时间复杂度较高，光是两重for循环就是O（n*n），同时还有两个字符串进行比较的时间消耗，时间复杂度势必大于O（n2）。然后细读题目，其中说到只包含小写字母，沿着这个提示，这一下子可以将字符串比较的难度降低了，我们想到了通过位运算的方式来降低比较带来的时间消耗，位运算的时间复杂度可以做到O（1），所以这样操作后，整体的时间复杂度就只有O（n2）。
初始化一个长度为26的数组： [0][0][0][0][0][0][0][0][0][0][0][0]0][0][0][0][0][0]0][0][0][0][0][0][0][0]，低位从a开始到z，每个字符与‘a’进行比较后，找到对应的数组位置，比如‘c’，那么下标为‘c’ - ‘a’ = 2，我们通过将1左移的方式，移动两位，及 1<<2,此时数组变成[0][0][0][0][0][0][0][0][0][0][0][0]0][0][0][0][0][0]0][0][0][0][0][1][0][0]，然后将移动后的值与最初的值进行或运算，这样一个字符串中的字符在数组对应的位置都会被更新为1，然后我们将两个字符串进行比较的时候，再将位运算得到的结果进行一次与操作，如果结果为0，则说明两个字符串中不存在相同的字符

代码如下

func maxProduct(words []string) int {
    length := len(words)
    mask := make([]int, length)
    for i := 0; i < length; i++ {
        mask = append(mask, 0)
    }
    for i := 0; i < length; i++ {
        curWord := words[i]
        for j := 0; j < len(curWord); j++ {
            mask[i] |= 1 << (curWord[j] - 'a')
        }
    }
    result := 0
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            if mask[i] & mask[j] == 0 {
                curMul := len(words[i]) * len(words[j])
                if curMul > result {
                    result = curMul
                }
            }
        }
    }
    return  result
}

进一步的优化

由于本题是求长度的最大值，所以我们没必要把所有的字符串都进行计算，我们可以把相同的位运算结果，只记录最大长度，这样可以减少比较的次数，代码如下

func maxProduct(words []string) int {
        length := len(words)
    /*var mask []int
    for i := 0; i < length; i++ {
        mask = append(mask, 0)
    }*/
    mask := make([]int, length)
    maskMap := make(map[int]int, length)
    for i := 0; i < length; i++ {
        curWord := words[i]
        for j := 0; j < len(curWord); j++ {
            mask[i] |= 1 << (curWord[j] - 'a')
        }
        v, ok := maskMap[mask[i]]
        if !ok  {
            maskMap[mask[i]] = len(curWord)
        }else {
            if len(curWord) > v {
                maskMap[mask[i]] = len(curWord)
            }
        }
    }
    result := 0
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            if mask[i] & mask[j] == 0 {
                vi , _ := maskMap[mask[i]]
                vj , _ := maskMap[mask[j]]
                curMul := vi * vj
                if curMul > result {
                    result = curMul
                }
            }
        }
    }
    return  result
}