[java/29ms] mask || two pointer. 4 versions for all, explained in detail.


  • 0

    The stats graph doesn't work today, so I can't see the percentage.

    public int maxProduct(String[] words) {
            Arrays.sort(words, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.length() - s2.length();
                }
            });
            
            int max = 0, mask[] = new int[words.length];
            for (int i = 0; i < words.length; i++) {
                for (char c : words[i].toCharArray())
                    mask[i] |= 1 << (c - 'a');
            }
    
            for (int i = words.length-1; i > 0; i--) {
                int len = words[i].length(), maski = mask[i];
                if (len * len <= max)
                    return max;
    
                for (int j = i-1; j >= 0; j--) {
                    if ((mask[j] & maski) == 0) {
                        max = Math.max(max, len * words[j].length());
                        break;
                    }
                }
            }
            return max;
        }
    

    My original version, using char[26] instead of 26 bits, dumb solution. :)

        // 64 ms
        public int maxProduct_1(String[] words) {
            Arrays.sort(words, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.length() - s2.length();
                }
            });
            int max = 0;
            boolean[] set = new boolean[26];
            for (int i = words.length-1; i > 0; i--) {
                int len = words[i].length();
                if (len * len <= max)
                    return max;
                // set
                for (char ch: words[i].toCharArray())
                    set[ch-'a'] = true;
    
                for (int j = i-1; j >= 0; j--) {
                    String tmp = words[j];
                    int k = 0;
                    for (; k < tmp.length(); k++) {
                        if (set[tmp.charAt(k) - 'a'])
                            break;
                    }
    
                    if (k == tmp.length()) {
                        max = Math.max(max, len * tmp.length());
                        break;
                    }
                }
                // clear the set
                Arrays.fill(set, false);
            }
            return max;
        }
    

    These two inspired by @StefanPochmann
    Using mask, great think to speed up program, though it will consume more space. (My version of boolean[] set = new boolean[26]; saves space but will take more time.)

        // 51 ms
        public int maxProduct_2(String[] words) {
            // use 26 bits to do this.
            int mask[] = new int[words.length];
            // -> boolean[] set = new boolean[26];
            for (int i = 0; i < words.length; i++) {
                for (char ch : words[i].toCharArray()) {
                    mask[i] |= 1 << (ch - 'a');
                }
            }
    
            int max = 0;
            for (int i = 0; i < words.length-1; i++) {
                int len = words[i].length();
                for (int j = i+1; j < words.length; j++) {
                    if ((mask[i] & mask[j]) == 0) {
                        max = Math.max(len * words[j].length(), max);
                    }
                }
            }
            return max;
        }
    
        // 73ms, using the hash map is a heavy work
        // this method only use the max length of each mask.
        public int maxProduct_3(String[] words) {
            HashMap<Integer, Integer> mask = new HashMap<>();
            int res = 0;
            for (String word : words) {
                int msk = 0, len = word.length();
                for (char ch : word.toCharArray()) {
                    msk |= 1 << (ch - 'a');
                }
    
                if (mask.containsKey(msk)) {
                    mask.put(msk, Math.max(len, mask.get(msk)));
                } else {
                    mask.put(msk, len);
                }
    
                for (Map.Entry<Integer, Integer> m : mask.entrySet()) {
                    if ((m.getKey() & msk) == 0) {
                        res = Math.max(res, m.getValue() * len);
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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