記錄一道使用位操作符的字符串比較算法

QiuyueZhong 發(fā)布于2019-08-23 11:47 / 1488人閱讀

摘要：是按位或二進(jìn)制編碼中，每一位兩者其中一個為，則為，否則，則為，因此就是對每一個字符合并，例如是，是，也是，是，是。

原題目：
給定一個字符串?dāng)?shù)組，找到長度的最大值length(word[i]) * length(word[j])，其中兩個單詞中的字母無相同。您可以假定每個單詞只包含小寫字母。如果沒有這兩個詞，返回0。

例：

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

解析：
這題肯定要進(jìn)行交叉對比(2個for循環(huán))，但最關(guān)鍵的就是對比過程，也就是判斷2個字符串是否存在相同的字符。

如果使用indexOf或者數(shù)組下標(biāo)記錄都會造成時間復(fù)雜度大幅提升，看了他人的答案發(fā)現(xiàn)使用的是位操作符<<，|和&，而且是在交叉對比之前進(jìn)行預(yù)處理，交叉對比的時候只需要簡單的判斷pretreate[i] & pretreate[j]===0便可，

因為使用后效率提升太多，解析并且記錄一下。

先解釋val |= (1 << (word.charCodeAt(i)-aCode))：

word.charCodeAt(i)-aCode這個很好懂，也就是a對應(yīng)0，b對應(yīng)1...這里的0,1數(shù)字代表的是
二進(jìn)制1后面的位數(shù)。

1<<0，1<<1是什么呢？

1在二進(jìn)制中(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)。

|是按位或：二進(jìn)制編碼中，每一位兩者其中一個為1，則為1，否則，則為0，

因此 val |=就是對每一個字符合并，例如

ab 是 00010|00001=>00011，

f 是 100000，

ffff 也是 100000，

big是 101000010，

axdg是100000000000000001001001。

&，按位與，二進(jìn)制編碼中，每一位兩者都為1，則為1，否則，則為0，

例1：axdg和oigd要判斷是否有重復(fù)：

axdg是：100000000000000001001001

oifd是：         100000100101000

& 后：  000000000000000000001000

因為第4位都為1，所以最后不為0，也可得知重復(fù)的就是字母表第4位：d。
?
例2：axdg和lkmk要判斷是否有重復(fù)：

結(jié)果為0，說明無重復(fù)。

axdg是：100000000000000001001001

lkmk是：           1110000000000

& 后：  000000000000000000000000

總結(jié)：這種方法使用了二進(jìn)制數(shù)字的位數(shù)作為保存字符的手段，相比起數(shù)組，散列表等，速度更快，在保存量較小(<=32)優(yōu)勢非常明顯。

代碼：

/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function(words) {
    let aCode="a".charCodeAt(0)
    function compute(word){
        let val=0
        for(let i=0;imaxSum && (pretreatment[i] & pretreatment[j])===0){
                 maxSum=len1*len2
            }
        }
    }
    return maxSum
};