56ms Java Solution. Pruned O(n^2)


  • 1
    Y

    This is my solution. I sort the word list first and then pruned a lot many 'useless' pairs. In practice, the time complexity is smaller than O(n^2). I don't know how to improve it.

    public class Solution {
        public int maxProduct(String[] words) {
            Arrays.sort(words, new LengthCompare());
            int res = 0;
            int[] bit = new int[words.length];
            for (int i = 0; i < words.length; i++)
                for (int j = 0; j < words[i].length(); j++)
                    bit[i] |= (1<<(words[i].charAt(j)-'a'));
            for (int i = 0; i < words.length-1 && words[i].length()*words[i].length() > res; i++)
                for (int j = i+1; j < words.length && words[i].length()*words[j].length() > res; j++)
                    if ((bit[i] & bit[j]) == 0)
                        res = words[i].length()*words[j].length();
            return res;
        }
        private static class LengthCompare implements Comparator<String>{
            public int compare(String s1, String s2){
                return (s2.length() - s1.length());
            }
        }
    }

  • 0
    Y

    For second outer for loop

    i < words.length-1
    

    Should it be

    i < words.length
    

    ?


  • 0
    S

    Hi, YujuaBao, maybe I misunderstood, but given that you sort the array in ascending order by length, in the 2nd double-loop, do u mean to go with decreasing order for index to take advantage of the sorted words array?


Log in to reply
 

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