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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

LEETCODE 438. Find All Anagrams in a String 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 567. Permutation in String 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

电子邮件地址不会被公开。