首页 > 代码库 > 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