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

原题链接

使用的方法

• Map.equals(): 判断两个 Map 是否包含完全相同的键值对。
• Map.getOrDefault(): 获取指定键的值，如果键不存在则返回默认值。
• Map.remove(): 从 Map 中移除指定键及其对应的值。

解题思路

• 使用滑动窗口和哈希表来记录当前窗口内的字符及其出现次数。
• 初始化一个哈希表 need 来记录字符串 p 中每个字符及其出现次数。
• 初始化一个哈希表 window 来记录当前窗口内每个字符及其出现次数。
• 首先将字符串 s 的前 p.length() 个字符加入 window 中，并检查是否与 need 相等，如果相等，则将起始索引 0 加入结果列表。
• 然后从索引 p.length() 开始遍历字符串 s，每次移动窗口时：
  • 将新字符加入 window 中。
  • 将旧字符从 window 中移除，如果该字符的出现次数为 0，则从 window 中完全移除该键。
  • 检查 window 是否与 need 相等，如果相等，则将当前窗口的起始索引加入结果列表。

代码实现

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

        Map<Character,Integer> need = new HashMap<>();
        for(char c:p.toCharArray()){
            need.put(c,need.getOrDefault(c,0) + 1);
        }

        int pLen = p.length();
        Map<Character,Integer> window = new HashMap<>();
        for(int i=0;i<pLen;i++){
            char c = s.charAt(i);
            window.put(c,window.getOrDefault(c,0)+1);
        }
        if(need.equals(window)){
            res.add(0);
        }

        for(int i = pLen; i<s.length();i++){
            char newChar = s.charAt(i);
            char oldChar = s.charAt(i-pLen);

            window.put(newChar,window.getOrDefault(newChar,0)+1);
            if(window.get(oldChar) == 1){
                window.remove(oldChar);
            } else {
                window.put(oldChar,window.get(oldChar) - 1);
            }

            if(need.equals(window)){
                res.add(i-pLen+1);
            }
        }
        return res;
    }
}