Group Anagrams

• Anagrams两种思路
  • 每个char的频率（还有一种做法就是用26个字母每个出现的频率来作为key）
  • 排序
• HashMap key和value的选择
  • 用sorted string作为key
  • 用List作为value

class Solution {
    //O(NKlogK)
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> results = new ArrayList<>();

        if (strs == null || strs.length == 0) {
            return results;
        }

        HashMap<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            char[] arr= strs[i].toCharArray();
            Arrays.sort(arr);
            String str = new String(arr);
            if (map.containsKey(str)) {
                map.get(str).add(strs[i]);
            } else {
                map.put(str, new ArrayList<>());
                map.get(str).add(strs[i]);
            }
        }

        //for (String s : map.keySet()) {
        //    results.add(map.get(s));
        //}
        //return results;

        //可以直接返回map里所有的值
        return new ArrayList(map.values());
    }
}

First Unique Character in a String

• int[26]可以用来保存所有字母的频率，int[256]可以保存所有的字符串

public class Solution {
    public int firstUniqChar(String s) {
        int freq [] = new int[26];
        for(int i = 0; i < s.length(); i ++)
            freq [s.charAt(i) - 'a'] ++;
        for(int i = 0; i < s.length(); i ++)
            if(freq [s.charAt(i) - 'a'] == 1)
                return i;
        return -1;
    }
}

Maximum Product of Word Lengths

• 利用二维数组来构建hashtable
• 对于common类的问题，可以用位运算。按位与可以用来比较。
  • 即把每个字母是否出现过编码成一个26位的数，letter[i] |= 1 << (ch - 'a')
  • 最后直接可以通过两个数按位与计算，如果出现相同的，则 != 0

public int maxProduct(String[] words) {
        int len = words.length;
        boolean[][] dict = new boolean[len][26];
        int ans = 0;

        for (int i = 0; i < len; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                dict[i][word.charAt(j)-'a'] = true;
            }
        }

        for (int i = 0; i < len; i++) {
            String word = words[i];
            for (int j = i+1; j < len; j++) {
                boolean flag = false;
                for (int k = 0; k < 26; k++) {
                    if (dict[i][k] && dict[j][k]) {
                        flag = true;
                        break;
                    }
                }

                if (flag)
                    continue;
                ans = Math.max(word.length() * words[j].length(), ans);
            }
        }

        return ans;
    }