给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
传入一个字符串数组,返回数组中两个不含相同字符的字符串元素长度乘积的最大值
思路
先暴力破解一下(暴力 API 工程师 ㄟ( ▔, ▔ )ㄏ )
实现
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function(words) {
let result = 0
// 校验两元素是否含有相同元素
const checkItem = (a, b) => {
let flag = false
for (let i of b) {
flag = flag || a.includes(i)
if (flag) return true
}
return flag
}
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if (!checkItem(words[i], words[j])) {
result = Math.max(result, words[i].length * words[j].length)
}
}
}
return result
}
上面方法借用 includes 方法去做两元素的检验,includes 本地的时间复杂度应该是 O,那么 checkItem 函数的时间复杂度应该是
对传入的字符串重新处理,用二进制位来标记字符串每个字符:
ab => ..000011
ac => ..0000101
df => ..0101000
实现
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function(words) {
let result = 0
// 校验两元素是否含有相同元素
const nums = words.map(item => {
let num = 0
for (let i = 0; i < item.length; i++) {
num = num | (1 << (item[i].charCodeAt() - 97))
}
return num
})
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if ((nums[i] & nums[j]) === 0) {
result = Math.max(result, words[i].length * words[j].length)
}
}
}
return result
}