[LeetCode]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.

代码如下：

public class Solution {
    
    public int (String[] words) {
        if(words == null || words.length == 0) return 0;
        
        int length = words.length;
        
        int[] masks = new int[length];
        //使用masks[i]记录words[i]含有的字符信息
        for(int i = 0; i < length; i++){
            //遍历words[i]的每个字符，masks[i]的最低比特位表示words[i]是否含有字符a(1表示含有
            //，0表示不含)，最高位表示是否含有字符z
            for(char ch: words[i].toCharArray()){
                masks[i] |= 1 << (ch - 'a');
            }
        }
        int maxProduct = 0;
        for(int i = 0; i < length; i++){
            for(int j = i+1; j < length; j++){
                //(masks[i] & masks[j]) == 0表示两个word没有相同的字符
                if((masks[i] & masks[j]) == 0){
                    maxProduct = Math.max(maxProduct, words[i].length()*words[j].length());
                }
            }
        }
        
        return maxProduct;
    }
}

或者优化一下：

1
2
3
4
5
6
7大专栏  [LeetCode]Maximum Product of Word Lengthsspan>
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


//我们还可以先对words数组按字符串长度排序，后面就可以进行剪枝优化,排序为O(nlgn)，不影响O(n*n)的时间复杂度
public int (String[] words) {
    if(words == null || words.length == 0) return 0;
    
    //对words数组按字符串长度排序
    Arrays.sort(words, new Comparator<String>(){
        public int compare(String a, String b){
            return b.length() - a.length();
        }
    });
    
    int length = words.length;
    int[] masks = new int[length];
    //使用masks[i]记录words[i]含有的字符信息
    for(int i = 0; i < length; i++){
        //遍历words[i]的每个字符，masks[i]的最低比特位表示words[i]是否含有字符a(1表示含有
        //，0表示不含)，最高位表示是否含有字符z
        for(char ch: words[i].toCharArray()){
            masks[i] |= 1 << (ch - 'a');
        }
    }
    int maxProduct = 0;
    for(int i = 0; i < length; i++){
        //words[i].length() * words[i].length()是words[i]最大可能的maxProduct
        if(words[i].length() * words[i].length() < maxProduct) break; //剪枝优化
        for(int j = i+1; j < length; j++){
            //(masks[i] & masks[j]) == 0表示两个word没有相同的字符
            if((masks[i] & masks[j]) == 0){
                maxProduct = Math.max(maxProduct, words[i].length()*words[j].length());
                break;//剪枝，越前面的字符串求到的maxProduct越大
            }
        }
    }
    
    return maxProduct;
}