前言
持续更新了
正文
问题来源
本问题来自leetcode上的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
解释: 不存在这样的两个单词。
分析：
题干说每个单词只包含小写字母，可以按位来记录该单词中有哪些字母。类似布隆过滤。
func max(a, b int) int {
if a > b {
return a
}
return b
}
func sbit(a string) int {
res := 0
for i := 0; i < len(a); i++ {
res |= 1 << (a[i] - 'a')
}
return res
}
func maxProduct(words []string) int {
wbits := make([]int, len(words))
for i := 0; i < len(words); i++ {
wbits[i] = sbit(words[i])
}
res := 0
for i := 0; i < len(words) - 1; i++ {
for j := i; j < len(words); j++ {
if wbits[i] & wbits[j] == 0 {
res = max(res, len(words[i]) * len(words[j]))
}
}
}
return res
}
总结：
勤思考。
结语
不管怎么样好好加油。
