Java O(n^2) using bits


  • 0
    Q
    public int maxProduct(String[] words) {
        int[] vals = new int[words.length];
        for (int j=0;j<words.length;j++){
            int val = 0;
            for (char c: words[j].toCharArray())
                 val = val|1<<(c-'a');
            vals[j]=val;
        }
        int max = 0;
        for (int i=0;i<vals.length;i++)
            for (int j=i+1;j<vals.length;j++)
               max=(vals[i]&vals[j])!=0?max:Math.max(max,words[i].length()*words[j].length());               
        return max;
    }

Log in to reply
 

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