My java solution (12ms) O(n*n)


  • 11
    D
    public class Solution {
    public int maxProduct(String[] words) {
        int len = words.length;
        int[] mark = new int[len];
        int[] leng = new int[len];
        for (int i = 0;i<len;i++) {
            int k = words[i].length();
            leng[i] = k;
            for (int j=0;j<k;j++) {
                int p = (int)(words[i].charAt(j)-'a');
                p = 1 << p;
                mark[i] = mark[i] | p;
            }
        }
        int ans = 0;
        for (int i = 0;i<len;i++)
         for (int j = i+1;j<len;j++) 
         if ((mark[i]&mark[j])==0) 
          if (ans<leng[i]*leng[j])
             ans=leng[i]*leng[j];
        return ans;
        }
    }
    

    The array store the length is necessary. If we calculate the length every time we need it, it will be very slow.


  • 0
    S

    Could you explain why we don't need to sort the strings by their lengths in the first place?


  • 2
    H

    The java source code for String.length() is to return a count member variable. I don't understand why we need to cache the lengths for all strings here.


  • 0
    H

    Actually I just tried your code, and it ran for 39ms... I guess the OJ added some new test cases after you submitted and posted.


  • 0
    S

    I just tried it twice and both were in 13ms. Are you sure that you did everything as I did?


  • 0
    H

    weird...I tried again and got 32ms. Just copied and pasted the code.


  • 0
    B
    This post is deleted!

Log in to reply
 

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