318. Maximum Product of Word Lengths

迷南。 2022-07-29 11:50 157阅读 0赞

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.

方法转自http://www.jianshu.com/p/bb84b0f866c9

问题关键在于判断两个字符串是否含有相同的字符。这里有一个好方法：因为我们不关心字符串是什么，只关心字符串中含有哪些字符，于是可以将每个字符串用一个int类型表示，a~z每个字母使用一位来存储（该位为1表示有这个字母，该位为0表示没有这个字母）。两个字符串没有相同字母则按位与的结果为0.

public class Solution {
        public int maxProduct(String[] words) {
            if(words == null || words.length == 1){
                return 0;
            }
            int n = words.length;
            int[] wordsInt = new int[n];
            for(int i=0;i<n;i++){
                wordsInt[i] = 0;
                for(int j=0;j<words[i].length();j++){
                    wordsInt[i] |= (1 << words[i].charAt(j)-'a');
                }
            }
            int max = 0;
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    if((wordsInt[i] & wordsInt[j]) == 0 && words[i].length()*words[j].length() > max){
                        max = words[i].length()*words[j].length();
                    }
                }
            }
            return max;
        }
    }