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

  • 11
    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])
        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

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

  • 2

    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

    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

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

  • 0

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

  • 0
    This post is deleted!

Log in to reply

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