最大单词长度乘积
题目:
给定一个字符串数组 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
解释: 不存在这样的两个单词。
抛砖引玉
传入一个字符串数组，返回数组中两个不含相同字符的字符串元素长度乘积的最大值
思路
先暴力破解一下（暴力 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 函数的时间复杂度应该是
对传入的字符串重新处理，用二进制位来标记字符串每个字符：
- 英文字母编码从 97(a)，那么我们就选对字符串所有字母减 97 方便位运算（题目中：你可以认为每个单词只包含小写字母。这不呼应上了嘛！）
- 一个字符串用一个二进制数表示，每个字符根据字符在二进制位中不同位置放置 1 占位，那么比较两个字符串是有相同字符只有对两个二进制数取按位或一定不等于 0
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
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
