Straightforward O(n^2) solution by comparing each word


  • 2
    M
    public class Solution {
        public int maxProduct(String[] words) {
            if (words == null || words.length == 0) return 0;
            
            int result = 0;
            for (int i = 0; i < words.length; i++) {
                int[] letters = new int[26];
                for (char c : words[i].toCharArray()) {
                    letters[c - 'a'] ++;
                }
                for (int j = 0; j < words.length; j++) {
                    if (j == i) continue;
                    int k = 0;
                    for (; k < words[j].length(); k++) {
                        if (letters[words[j].charAt(k) - 'a'] != 0) {
                            break;
                        }
                    }
                    if (k == words[j].length()) {
                        result = Math.max(result, words[i].length() * words[j].length());
                    }
                }
            }
            return result;
        }
    }

  • 2
    N

    This throws "time limited exceeded" error in my case. Were you able to get this excepted???


  • 0
    L

    optimization:
    j can start from i + 1 instead of 0, which saves time for duplicate word pair check.
    and "if (j == i) continue;" can be get rid of.


Log in to reply
 

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