力扣438——找到字符串中所有字母异位词

这道题主要是利用"窗口"这一概念，优化的时候可以利用题目本身的特殊性。

原题

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

原题url：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

解题

利用"窗口"思想

这道题类似字符串完全匹配，只是这道题要求连续但顺序可以不一致。这样就无法利用待匹配字符串预先构造了。

那么结合这道题，为了能够让我们知道当前字符是否在待匹配字符串中，我们需要一个集合存储。

为了能够让我们知道各个字符出现了几次，我们需要一个哈希表，并且实时更新其次数，如果次数为0，则移除该项，如果哈希表为空，则说明找到了，记录开始下标，并且窗口滑动。

结合上面的思路，我们可以写出代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 最终结果
        List<Integer> result = new LinkedList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        // 根据p构造map，key代表字符，value代表相应次数
        Map<Character, Integer> map = new HashMap<>();
        for (Character character : p.toCharArray()) {
            map.put(character, map.getOrDefault(character, 0) + 1);
        }
        // p中所有的字符
        Set<Character> pCharSet = new HashSet<>(map.keySet());
        // 每个字母出现的位置，value表示每一次出现的下标
        Map<Character, LinkedList<Integer>> indexMap = new HashMap<>();
        // 开始的下标
        int first = 0;
        char[] sArray = s.toCharArray();
        // 遍历s
        for (int i = 0; i < sArray.length; i++) {
            Character character = sArray[i];
            // 如果character不在pCharSet中，说明该字符不存在
            if (!pCharSet.contains(character)) {
                // 则重新构造indexMap
                indexMap = new HashMap<>();
                // 从first位置到i位置，还原map
                for (int j = first; j < i; j++) {
                    character = sArray[j];
                    map.put(character, map.getOrDefault(character, 0) + 1);
                }
                // 重置first的位置
                first = i + 1;
                continue;
            }

            // 从indexMap中获取该字符出现的位置
            LinkedList<Integer> indexList = indexMap.computeIfAbsent(character, k -> new LinkedList<>());
            // 在末尾记录当前位置
            indexList.add(i);
            // map中相应字符剩余出现次数
            Integer count = map.get(character);
            // 如果次数为null，说明无法再减
            if (count == null) {
                // 从开始下标到该字符第一次出现的下标，还原map和indexMap
                int firstIndex = indexList.removeFirst();
                for (int j = first; j < firstIndex; j++) {
                    character = sArray[j];
                    map.put(character, map.getOrDefault(character, 0) + 1);
                    indexMap.get(character).removeFirst();
                }
                // 重置first的位置
                first = firstIndex + 1;
                continue;
            }

            // 次数-1
            count--;
            // 如果次数不为0，则重新放进map中
            if (count > 0) {
                map.put(character, count);
                continue;
            }

            // 如果次数减为0，则移除该项
            map.remove(character);
            // 检查map是否为空
            if (!map.isEmpty()) {
                continue;
            }

            // 如果为空，说明满足条件，记录进result中
            result.add(first);
            // first向后移动1个（窗口滑动）
            character = sArray[first];
            map.put(character, map.getOrDefault(character, 0) + 1);
            indexMap.get(character).removeFirst();
            first++;
        }

        return result;
    }
}

提交OK，但执行用时很慢，需要优化。

优化

上面解法查询慢，我感觉根本原因在于使用了比较复杂的数据结构，包括集合、哈希表、链表等，虽然 Java 中针对这些结构做了优化，但相比于最基础的结构数组而言，在查找和更新上还是更慢了。这道题可以用数组的主要原因在于只会出现26个小写英文字母。这样用了数组之后，查找和更新都快了太多。大家可以根据这个思路优化试试。

既然有提到窗口，那么我们就将这个思想用到极致。可以先将窗口设置的大一些，比如至少包含目标字符串里的所有字符。达成条件后，就开始把左边开始缩小，直到缩小成目标字符串的长度后，然后记录进结果中，之后窗口右移，重复上述过程。

接下来看看代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s == null || s.length() == 0) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        // 需要的字符，由于都是小写字母，因此直接用26个长度的数组代替原来的HashMap
        int[] needs = new int[26];
        for(char ch : p.toCharArray()) {
            needs[ch - 'a'] ++;
        }
        // "窗口"
        int[] window = new int[26];
        // 窗口的左右下标
        int left = 0, right = 0;
        // 用total检测窗口中是否已经涵盖了p中的所有字符
        int total = p.length();
        // 遍历s
        while(right < s.length()) {
            char chr = s.charAt(right);
            // 如果该字符在p中出现过
            if(needs[chr - 'a'] > 0) {
                // 则在窗口中记下该字符
                window[chr - 'a'] ++;
                // 如果当前窗口中该字符的数量，小于需要的数量
                if(window[chr - 'a'] <= needs[chr - 'a']) {
                    // 则total数量减1
                    total --;
                } 
            }
            // total为0，说明窗口中包含了p中所有字符
            while(total == 0) {
                // (right - left + 1)代表窗口的大小
                // 如果窗口的大小等于p，说明符合要求
                if(right - left + 1 == p.length()){
                    // 记录左指针
                    res.add(left);
                } 
                // 左指针向右移动1个
                char chl = s.charAt(left);
                left ++;
                // 如果左指针属于p中
                if(needs[chl - 'a'] > 0) {
                    // 那么窗口中该字符的数量也需要减1
                    window[chl - 'a'] --;
                    // 如果窗口中该字符的数量小于需要的数量
                    if(window[chl - 'a'] < needs[chl - 'a']) {
                        // 则total加1，跳出循环，说明还需要继续向右寻找
                        total ++;
                    } 
                }
            }
            // 继续向右寻找
            right ++;
        }
        return res;
    }
}

提交OK，执行时间加快了一个量级。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是利用"窗口"这一概念，优化的时候可以利用题目本身的特殊性。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道