242. Valid Anagram

49. Group Anagrams

比较 Trivial 的问题。

这题主要的乐趣在于怎么把多个是 anagram 的 string 映射到同一个 key 上。简单的办法是排序。

或者开个 int[] 统计字母数量，然后生成一个类似于 1a2b4f 这种的 string signature

除此之外比较 fancy 的写法是利用 prime number 做 string hashing，容错率不太好而且我觉得用 prime number 总是要去证明一下算法的正确性，不太适用于面试。

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        if (strs == null || strs.length == 0) return result;
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String sortedChars = new String(array);

            if (!map.containsKey(sortedChars)) {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(sortedChars, list);
            } else {
                List<String> list = map.get(sortedChars);
                list.add(str);
                map.put(sortedChars, list);
            }
        }
        for (String str : map.keySet()) {
            Collections.sort(map.get(str));
            result.add(map.get(str));   
        }
        return result;
    }
}

438. Find All Anagrams in a String

Substring Anagrams

最简单的想法就是像LC76，窗口类双指针里面那道题，两个hash判断valid。时间复杂度应该是nl的，l为短字符串的长度。

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (p == null || s == null) return result;

        int[] target = new int[128];
        for (int i = 0; i < p.length(); ++i) {
            target[p.charAt(i)]++;
        }
        for (int i = 0; i <= s.length() - p.length(); ++i) {
            int[] source = new int[128];
            for (int j = i; j < i + p.length(); ++j) {
                source[s.charAt(j)]++;
            }
            if (valid(source, target)) result.add(i);
        }
        return result;
    }
    private boolean valid(int[] source, int[] target) {
        for (int i = 0; i < source.length; ++i) {
            if (source[i] != target[i]) return false;
        }
        return true;
    }
}

优化就是用sliding window做。见Sliding Window。