HashMap+bitmask


  • 0
    F

    I don't know why my solution is slower than best votes one.

    public int maxProduct(String[] words) {
            if (words.length < 2) return 0;
            Map<Integer, Integer> map = new HashMap<>();
            int res = 0;
            for (int i = 0; i < words.length; i++) {
                int key = getKey(words[i]);
                for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                    if ((entry.getKey().intValue()&key) == 0) {
                       res = Math.max(res, entry.getValue()*words[i].length()); 
                    }
                }
                if (!map.containsKey(key) || map.get(key).intValue() < words[i].length()) {
                    map.put(key, words[i].length());
                }
            }
            return res;
        }
        private int getKey(String str) {
            int res = 0;
            for (int i = 0; i < str.length(); i++) {
                res |= (1<<(str.charAt(i)-'a'));
            }
            return res;
        }

Log in to reply
 

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