记录一道使用位操作符的字符串比较算法
文章目录
原题目:
给定一个字符串数组,找到长度的最大值length(word[i]) * length(word[j]),其中两个单词中的字母无相同。您可以假定每个单词只包含小写字母。如果没有这两个词,返回0。
例:
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
解析:
这题肯定要进行交叉对比(2个for循环),但最关键的就是对比过程,也就是判断2个字符串是否存在相同的字符。
如果使用indexOf或者数组下标记录都会造成时间复杂度大幅提升,看了他人的答案发现使用的是位操作符<<,|和&,而且是在交叉对比之前进行预处理,交叉对比的时候只需要简单的判断pretreate[i] & pretreate[j]===0便可,
因为使用后效率提升太多,解析并且记录一下。
先解释val |= (1 << (word.charCodeAt(i)-aCode)):
-
word.charCodeAt(i)-aCode这个很好懂,也就是a对应0,b对应1...这里的0,1数字代表的是
二进制1后面的位数。 -
1<<0,1<<1是什么呢?1在二进制中(32位)就是
00000000000000000000000000000001,<<是左移1位,那么
1<<0还是1,1<<1就是(前面的零省略)10,1<<2就是100,1<<3就是1000,于是可知
a就是1,b是10,c是100...z是10000000000000000000000000(25个0)。 -
|是按位或:二进制编码中,每一位两者其中一个为1,则为1,否则,则为0,因此
val |=就是对每一个字符合并,例如ab是00010|00001=>00011,f是100000,ffff也是100000,big是101000010,axdg是100000000000000001001001。 -
&,按位与,二进制编码中,每一位两者都为1,则为1,否则,则为0,例1:
axdg和oigd要判断是否有重复:axdg是:100000000000000001001001 oifd是: 100000100101000 & 后: 000000000000000000001000因为第4位都为1,所以最后不为0,也可得知重复的就是字母表第4位:
d。
例2:axdg和lkmk要判断是否有重复:结果为0,说明无重复。
axdg是:100000000000000001001001 lkmk是: 1110000000000 & 后: 000000000000000000000000
总结:这种方法使用了二进制数字的位数作为保存字符的手段,相比起数组,散列表等,速度更快,在保存量较小(<=32)优势非常明显。
代码:
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function(words) {
let aCode='a'.charCodeAt(0)
function compute(word){
let val=0
for(let i=0;i<word.length;i++){
val |= (1 << (word.charCodeAt(i)-aCode))
}
return val
}
let pretreatment=[]
for(let i=0;i<words.length;i++){
pretreatment[i]=compute(words[i])
}
let maxSum=0
for(let i=0;i<words.length-1;i++){
for(let j=i+1;j<words.length;j++){
let len1=words[i].length,len2=words[j].length
if(len1*len2>maxSum && (pretreatment[i] & pretreatment[j])===0){
maxSum=len1*len2
}
}
}
return maxSum
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论