32ms Java AC solution


  • 70
    C
    public class Solution {
        public int maxProduct(String[] words) {
            int max = 0;
    
            Arrays.sort(words, new Comparator<String>(){
                public int compare(String a, String b){
                    return b.length() - a.length();
                }
            });
    
            int[] masks = new int[words.length]; // alphabet masks
    
            for(int i = 0; i < masks.length; i++){
                for(char c: words[i].toCharArray()){
                    masks[i] |= 1 << (c - 'a');
                }
            }
        
            for(int i = 0; i < masks.length; i++){
                if(words[i].length() * words[i].length() <= max) break; //prunning
                for(int j = i + 1; j < masks.length; j++){
                    if((masks[i] & masks[j]) == 0){
                        max = Math.max(max, words[i].length() * words[j].length());
                        break; //prunning
                    }
                }
            }
    
            return max;
        }
    }

  • 0
    G

    How would this work on the following words: "abcde", "fg","hijklmnop"
    seems that you'll calculate "abcde" * "fg" and then break before calculating the correct answer.
    Or perhaps I'm not fully understanding your solution.


  • 0
    C
    1. The array is sorted as {"hijklmnop", "abcde", "fg"}.
    2. The "break" only breaks out the inner "for" loop

  • 0
    G

    yes, I realized this later. Thanks for responding.


  • 0
    L

    I think there is no need to sort


  • 0
    H

    I think it is necessary for pruning.


  • 0
    Z

    Since the overall complexity is O(n^2), sorting does not matter too much. Sorting will enable early pruning.


  • 0
    S

    i'm a little bit confused about that “if(words[i].length() * words[i].length() <= max) break; //prunning” ?why if the square of words[i].length smaller than max then break?


  • 3
    J

    That's what sorting is for. So that you can exit if squaring is not larger than the max. Because if you keep going, the product will not get larger.


  • 0
    J

    And I just tested it without sorting and it's 19 ms. So the nlog(n) could be significant I suppose...


  • 0
    I
    This post is deleted!

  • 0
    T

    A slight optimization is moving the second for loop into the first one, so the first loop can end early with pruning before calculating the masks for words with small lengths


  • 0
    D

    Can someone explain how he is sure that if the AND of two masked number is Zero, then those are always different (no common characters)?


  • 0

    yes, i also test it in Python, got 78ms without sorting, while 78ms with sorting... but it is worth trying~


  • 0

    my python version:

    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        n = len(words)
        def my_cmp(a,b):
            return len(b)-len(a)
        sorted_words = sorted(words, my_cmp)#seem not save time :(
    
        mask = [0]*n
        count = [0]*n
        begin_ord = ord('a')
        for i, w in enumerate(sorted_words):
            for c in w:
                mask[i] |= 1<<ord(c)-begin_ord
                count[i] += 1
        max_len = 0
        for i in range(n):
            if count[i]**2<max_len:
                continue
            for j in range(i+1, n):
                
                if mask[i]&mask[j]==0:
                    multiple = count[i]*count[j]
                    if multiple>max_len:
                        max_len = multiple
                        break
        return max_len

  • 0
    V

    Came to the same solution without sort and pruning. The only benefit of sorting the input array is pruning. But it's hard to prove that the gain of pruning will cover the cost of sorting since it takes O(nlogn) time.


  • 1
    X

    try to simplify it with Java 8:

        Arrays.sort(words, (a, b) -> b.length() - a.length());
        
        int[] masks = new int[words.length];
        for (int i = 0, len = words.length; i < len; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                masks[i] |= 1 << (words[i].charAt(j) - 'a');
            }
        }
        
        int max = 0;
        for (int i = 0, len = words.length; i < len; i++) {
            if (words[i].length() == 0) {
                continue;
            }
            for (int j = i + 1, minLen = max / words[i].length(); j < len && words[j].length() > minLen; j++) {
                if ((masks[i] & masks[j]) == 0 && words[i].length() * words[j].length() > max) {
                    max = words[i].length() * words[j].length();
                    break;
                }
            }
        }
        
        return max;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.