问题描述
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
Output: 16
Explanatio: The two words can be “abcw”, “xtfn”.
Example 2:
Input: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output: 4
Explanation: The two words can be “ab”, “cd”.
Example 3:
Input: words = [“a”,“aa”,“aaa”,“aaaa”]
Output: 0
Explanation: No such pair of words.
Constraints:
- 2 <= words.length <= 1000
- 1 <= words[i].length <= 1000
- words[i] consists only of lowercase English letters.
问题分析
题目要求没有相同字符串的最大长度乘积，首先想到的是最朴素的方式，即按照长度对字符串数组倒序排序后，依次向后计算不含相同字符串的长度乘积，每找到一个这样的字符串对，就可以移动到下一个字符串继续计算；在过程中，利用map来计算2个字符串不存在相同字符。 代码如下：
初始解法
// brute force
func maxProduct(words []string) int {
sort.Slice(words, func(i, j int) bool {
return len(words[i]) > len(words[j])
})
ans := 0
for i := 0; i < len(words)-1; i++ {
m := make(map[byte]int)
// 将字符串words[i]各个字符出现的数量进行统计
for j := 0; j < len(words[i]); j++ {
m[words[i][j]]++
}
for j := i + 1; j < len(words); j++ {
intersect := false
// 依次check字符串words[j]中各个字符是否在words[i]是否有出现
for k := 0; k < len(words[j]); k++ {
if _, ok := m[words[j][k]]; ok {
intersect = true
break
}
}
if !intersect {
ans = max(ans, len(words[i])*len(words[j]))
break
}
}
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
优化解法
上述解法提交AC后，耗时还是略久。重新思考下更高效的解法
因为要计算任意2个字符串之间是否可能符合条件，那么两两比较这里的复杂度感觉很难去优化了。剩下能优化的就是如何判断2个字符串含有相同字符。前面的解法里，使用map去做会稍显笨重。
思考了一阵后，考虑到字符串仅由小写字母构成，也就是说字符的范围只有26个，那么可以使用int类型按位去表示。具体来说，就是:
a b c
↕️ ↕️ ↕️
1 1 1 0 0 0 0 0 0 0 0… (为方便展示，左侧是低位)
对于字符串abc，就用二进制的 111000… (左侧为低位)来表示
用二进制最低位1表示字符串中出现了字符a，第二位为1表示字符串中出现了字符b，以此类推
这样，字符串就被转换成了一个整数，这时要判断是否有相同字符，只要两个整数进行与操作即可，如果结果不为0，说明存在相同字符
想通这层后，优化后的代码如下:
func maxProduct(words []string) int {
ans := 0
sort.Slice(words, func(i, j int) bool {
return len(words[i]) > len(words[j])
})
bits := []int{}
for i := 0; i < len(words); i++ {
// 将字符串转换为对应的整数
bits = append(bits, transfer2bit(words[i]))
}
for i := 0; i < len(words)-1; i++ {
for j := i + 1; j < len(words); j++ {
// 进行与操作，结果不为0，说明存在相同字符，跳过
if bits[i]&bits[j] > 0 {
continue
}
// 更新ans
ans = max(ans, len(words[i])*len(words[j]))
break
}
}
return ans
}
func transfer2bit(word string) int {
ans := 0
// 依次将ans对应位上设置成1
for i := 0; i < len(word); i++ {
// 使用或操作，来处理相同字符出现多次的情况
ans |= 1 << (word[i] - 'a')
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}