LEETCODE 438. Find All Anagrams in a String 解题思路分析

题目大意：

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

给定一个字符串 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" 的字母异位词。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=438

解题思路分析：

看到求字符串区间的题目我们应该下意识想到使用双指针（或者滑动窗口）来解题。这里说句题外话，Leetcode中大部分题目实际上都存在着一定的解题套路，一般情况下我们看到某些条件或者某些关键字时，就应该马上联想到使用什么思路来破解。比如看到树形结构时应联想到dfs或者bfs；看到返回结果会很大时（例如需要对10^9+7取模）应马上意识到这很可能是动态规划的题目；再比如本题这种求子串或者子数组类型的问题，首先要想到双指针等等。一直以来都想总结一篇关于leetcode中解题套路的文章，但碍于时间原因一直没能着手（残念）。

回到本题，由于题目求的是异位词子串，因此单单比较子串是否相同是行不通的，这种情况下我们通常需要对字符串进行预处理，即统计出它包含的每一种字符的个数。因此解题时，我们需要先统计出字符串p中每一种字符的个数。然后再使用双指针思路，找出s中的合理区间子串（该子串包含的字符种类和个数与p中的元素相同）。

对于双指针思路，我们需要定义左右两个指针变量，初始时都在下标0的位置。左右指针所包含的区间即是当前子串范围。开始时，我们首先尝试向右移动1位右指针（扩大范围），右指针当前指向的字符即是范围扩大后新加入进来的字符，我们查看该字符在p中的个数，这时存在三种情况：

1. 如果p中不存在该字符（个数为0），说明s中包含当前字符的区间都是不合理区间，我们将左右指针同时移动到当前位置的下一位。
2. 如果当前区间内该字符个数小于p中该字符个数，说明当前区间内的字符个数还没到达p中的水平，可将当前区间内当前字符个数加一。加一操作后，查看当前区间内所有字符个数是否与p中相同，如果相同的话，当前区间是一个合理区间，返回结果加一。
3. 如果当前区间内该字符个数等于p中该字符个数，说明当前区间内该字符个数已满，再加上当前字符的话会超出p中相应的个数（多一个），此时应当尝试向右移动左指针（缩小区间范围），同时左指针对应字符在区间内的个数减一。直到区间内右指针的字符个数等于p中相应个数（不再多一个）为止，此时依旧需要查看当前区间内所有字符个数是否与p中相同，如果相同的话，当前区间是一个合理区间，返回结果加一。

实现代码：

public List<Integer> findAnagrams(String s, String p) {
    // 统计p中每种字符个数
    int[] pCount = new int[26];
    for(char c : p.toCharArray()){
        pCount[c-'a']++;
    }
    // s中当前区间内每种字符个数
    int[] sCount = new int[26];
    // 返回结果
    List<Integer> res = new ArrayList<>();
    // 左指针
    int left=0;
    // 循环右指针
    for(int right=0;right<s.length();right++){
        // 当前字符
        int c=s.charAt(right)-'a';
        if(pCount[c]==0){ // 当前字符在p中不存在
            left=right+1;
            sCount = new int[26];
            continue;
        }else if(sCount[c]<pCount[c]){ // 当前字符个数小于p中相应个数
            sCount[c]++;
            if(sCount[c]==pCount[c]&&isSame(sCount,pCount)){
                res.add(left);
            }
        }else if(sCount[c]==pCount[c]){ // 当前字符个数等于p中相应个数
            sCount[c]++;
            while(left<right){
                int lc=s.charAt(left)-'a';
                sCount[lc]--;
                left++;
                if(lc==c) {
                    if(isSame(sCount,pCount)){
                        res.add(left);
                    }
                    break;
                }
            }
        }
    }
    return res;
}

boolean isSame(int[] sCount, int[] pCount){
    for(int i=0;i<26;i++){
        if(pCount[i]!=sCount[i]) return false;
    }
    return true;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 85.80% of Java online submissions for Find All Anagrams in a String.

Memory Usage: 40.6 MB, less than 14.00% of Java online submissions for Find All Anagrams in a String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-438-find-all-anagrams-in-a-string-解题思路分析/