字母异位词

242. 有效的字母异位词

哈希表

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); ++i){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
        }
        for (int i = 0; i < t.length(); ++i){
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0)-1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()){
            if (entry.getValue() != 0)
                return false;
        }
        // map也有equals方法
        return true;
    }
}

排序

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

49. 字母异位词分组

哈希表+排序

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hm = new HashMap<>();
        for (String str : strs){
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String newStr = new String(chars); 
            //说下这里为什么要转成string，因为如果你用char数组，每次new以后地址不同，hash值也不相同
            //而string重写了hashcode和euqals方法，只要字符串一致hash的值是一样的
            List<String> list = hm.getOrDefault(newStr, new ArrayList<>());
            list.add(str);
            hm.put(newStr, list);
        }
        return new ArrayList<>(hm.values());
    }

438. 找到字符串中所有字母异位词

我不明白为什么下面这个做法会超时
别人的解释：

这个说的问题是，下面的滑动窗口里面的，跟我做的没有关系


我的做法：感觉这个不叫滑动窗口，时间复杂度好像还是，如果是排序，是，得想办法降到（subString在1.6之前的时间复杂度是O(1)，在1.6之后的时间复杂度是O(n)）

//原错误解法
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans= new ArrayList<>();
        if (s.length() < p.length()) {
            return ans;
        }
        int left = 0, right = p.length();
        while(right <= s.length()){
            String str = s.substring(left, right); //有人说是这里的问题
            if (isAnagram(str, p)){ //这里也是，都会让时间复杂度变成n方
                ans.add(left);
            }
            left++;
            right++;
        }
        return ans;
    }
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); ++i){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
        }
        for (int i = 0; i < t.length(); ++i){
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0)-1);
            if (map.get(t.charAt(i)) < 0)
                return false;
        }
        return true;
    }
}

//修改解法一：但是使用了hashmap自带的equals方法
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();
        HashMap<Character, Integer> mapp = new HashMap<>();
        HashMap<Character, Integer> maps = new HashMap<>();
        for (int i = 0; i < pLen; ++i){
            mapp.put(p.charAt(i), mapp.getOrDefault(p.charAt(i), 0)+1);
            maps.put(s.charAt(i), maps.getOrDefault(s.charAt(i), 0)+1);
        }

        if ( mapp.equals(maps) ) //不知道这里的时间复杂度会不会超时
            ans.add(0);

        for (int i = 0; i < sLen - pLen; ++i){
            //maps.put(s.charAt(i), maps.getOrDefault(s.charAt(i), 0)-1);
            maps.put(s.charAt(i), maps.get(s.charAt(i))-1);
            maps.put(s.charAt(i+pLen), maps.getOrDefault(s.charAt(i+pLen), 0)+1);
            if ( mapp.equals(maps) )
                ans.add(i+1);
        }
        return ans;
    }

    public boolean vs(Map<Character,Integer>  map1, Map<Character,Integer>  map2)
    {
        for(Character c:map1.keySet())
            if(!map2.getOrDefault(c, 0).equals(map1.get(c)))
                return false;
        return true;
    }
}

//修改解法二：不使用hashmap自带的equals方法
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();
        HashMap<Character, Integer> mapp = new HashMap<>();
        HashMap<Character, Integer> maps = new HashMap<>();
        for (int i = 0; i < pLen; ++i){
            mapp.put(p.charAt(i), mapp.getOrDefault(p.charAt(i), 0)+1);
            maps.put(s.charAt(i), maps.getOrDefault(s.charAt(i), 0)+1);
        }

        if ( vs(maps,mapp) ) //不知道这里的时间复杂度会不会超时
            ans.add(0);

        for (int i = 0; i < sLen - pLen; ++i){
            //maps.put(s.charAt(i), maps.getOrDefault(s.charAt(i), 0)-1);
            maps.put(s.charAt(i), maps.get(s.charAt(i))-1);
            maps.put(s.charAt(i+pLen), maps.getOrDefault(s.charAt(i+pLen), 0)+1);
            if ( vs(maps,mapp) )
                ans.add(i+1);
        }
        return ans;
    }

    public boolean vs(Map<Character,Integer>  map1, Map<Character,Integer>  map2)
    {
        for(Character c:map1.keySet())
            if(!map2.getOrDefault(c, 0).equals(map1.get(c)))
                return false;
        return true;
    }
}

使用HashMap的equals方法出错的原因：
因为字符串p的hashmap是不变的，也就是键值对不变，键和值不变；而在窗口移动的过程中，s对应的hashmap是不断变化的，首先就是有的字母对应的值会变为0，这样我们认为他是消失了，但是其键值对仍然存在于hashmap中。他长度都不一样，调用equals方法怎么可能相等呢。

//正确解法
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}