Java, no bit manipulation, 47 ms, straight-forward


  • 1
    N

    use int[][] counts = new int[words.length][26] to record the letters count for each words.

    public class Solution {
        public int maxProduct(String[] words) {
            if (words == null || words.length <= 1) {
                return 0;
            }
            
            int length = words.length;
            
            int[][] counts = new int[length][26];
            
            for (int i = 0; i < length; i++) {
                String cur = words[i];
                for (int j = 0; j < cur.length(); j++) {
                    char c = cur.charAt(j);
                    counts[i][c - 'a']++;
                }
            }
            
            int max = 0;
            
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    boolean canPair = true;
                    for (int k = 0; k < 26; k++) {
                        if (counts[i][k] != 0 && counts[j][k] != 0) {
                            canPair = false;
                            break;
                        }
                    }
                    if (canPair) {
                        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.