首页 > 代码库 > 318. Maximum Product of Word Lengths

318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

思路是利用小写字母是有限的,将string变成一个int,这样更好比较。比如“abcdefghijklmnopqrstuvwxyz” => 1...1, 一共26个1。 比较的时候如果两个string有相同的letter,那么

int1&int2 !=0。然后根据这个条件向前判断,求最大值就好了。

public int MaxProduct(string[] words) {        int res =0;         var s =new int[words.Count()];         for(int i=0;i< words.Count();i++)         {             string word = words[i];             for(int j=0;j<word.Length;j++)             {                                  s[i] |= 1<<(word[j]-a);              }                          for(int m= i-1;m>=0;m--)             {                 if((s[m] & s[i]) ==0) res = Math.Max(res,words[i].Length*words[m].Length);             }         }         return res;    }

 

318. Maximum Product of Word Lengths