GoJava算法最大單詞長度乘積示例詳解

第GoJava算法最大單詞長度乘積示例詳解目錄最大單詞長度乘積方法一：位運(yùn)算（java）方法一：位運(yùn)算（go）

最大單詞長度乘積

給你一個字符串?dāng)?shù)組words，找出并返回length(words[i])*length(words[j])的最大值，并且這兩個單詞不含有公共字母。如果不存在這樣的兩個單詞，返回0。

*示例1：

輸入：words=[abcw,baz,foo,bar,xtfn,abcdef]

輸出：16

解釋：這兩個單詞為abcw,xtfn。

示例2：

輸入：words=[a,ab,abc,d,cd,bcd,abcd]

輸出：4

解釋：這兩個單詞為ab,cd。

示例3：

輸入：words=[a,aa,aaa,aaaa]

輸出：0

解釋：不存在這樣的兩個單詞。

方法一：位運(yùn)算（java）

為了得到最大單詞長度乘積，樸素的做法是，遍歷字符串?dāng)?shù)組words中的每一對單詞，判斷這一對單詞是否有公共字母，如果沒有公共字母，則用這一對單詞的長度乘積更新最大單詞長度乘積。

題目約定了每個單詞僅包含小寫字母，所以，我們可以將單詞中的每個字母都映射到一個int類型的不同位上，這樣，就做到了每個單詞都對應(yīng)一個int類型的數(shù)值，這樣的話，我們對比兩個單詞是否包含相同的字母，只需要把它們對應(yīng)的int數(shù)值做運(yùn)算，看是不是等于0即可，如果等于0，說明沒有相同的位是1，也就不存在相同的字母。

這樣，我們在比較兩個單詞是否沒有公共字母的時候只要直接按位與一下即可，沒有公共字母應(yīng)該得到的值是0，其他情況得到的值都不為零。

classSolution{

publicintmaxProduct(String[]words){

MapInteger,Integermap=newHashMapInteger,Integer

intlength=words.length;

for(inti=0;ilength;i++){

intmask=0;

Stringword=words[i];

intwordLength=word.length();

for(intj=0;jwordLength;j++){

mask|=1(word.charAt(j)-'a');

if(wordLengthmap.getOrDefault(mask,0)){

map.put(mask,wordLength);

intmaxProd=0;

SetIntegermaskSet=map.keySet();

for(intmask1:maskSet){

intwordLength1=map.get(mask1);

for(intmask2:maskSet){

if((mask1mask2)==0){

intwordLength2=map.get(mask2);

maxProd=Math.max(maxProd,wordLength1*wordLength2);

returnmaxProd;

l：數(shù)組中所有單詞的長度之和

n：數(shù)組長度

時間復(fù)雜度：o（l+n^2）

空間復(fù)雜度：o（n）

方法一：位運(yùn)算（go）

具體的方法思路已經(jīng)在上文中表述，詳情請看上文內(nèi)容

funcmaxProduct(words[]string)int{

hash:=func(wordstring)int{

res:=0

for_,r:=rangeword{

res|=1(r-'a')

returnres

m,ans:=map[int]int{},0

for_,word:=rangewords{

h:=hash(word)

ifm[h]len(word){

forother,v:=rangem{

if((otherh)==0){

iftmp:=v*len(word);tmpans{

ans=tmp

m[h]=len(word)

returnans

l：數(shù)組中所有單詞的長度之和

n