10.Find All Anagrams in a String（在一个字符串中发现所有的目标串排列）

Level：

Easy

题目描述：

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings sand p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:

s: "cbaebabacd" p: "abc"

Output:

[0, 6]

Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".

The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:

s: "abab" p: "ab"

Output:

[0, 1, 2]

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".

The substring with start index = 1 is "ba", which is an anagram of "ab".

The substring with start index = 2 is "ab", which is an anagram of "ab".

思路分析：

知识点：滑动窗口

关键点一：像这种找子串的可以使用滑动窗口Sliding Window来做。这个窗口由left和right来约束[left,right]这个闭区间，刚开始知识left=right=0，然后left不变，right不断增长，直到到达某个值，left和right一起增长，这样就实现了窗口的创建和向下滑动。

关键点二：对于p中出现的字符以及次数需要记下来。可以使用一个数组ascaiiNums，长度为256，是因为ascaii一共只有256个，初始化的值表示角标对应的ascaii字符在p中出现的次数，那么没有出现过的就是0.之后如果s中出现过该字符，那么数组对应位置的值就减一。如果减之后的值大于等于0，就说明p中该字符出现了一次，这时p中未出现的字符数量count就减一。之所以要判断是>=0,是因为如果数组中原来的值是0（说明p中没有出现），那么减一后就成了负的，这种情况下p中剩下未出现的字符的count数值保持不变。如果count的值为0，说明p中的字符全出现了，找到一个符合条件的子串，left就是子串的首地址。之后要向右滑动窗口，移动的方法是left++,right++，更新p中未出现的字符个数count。

代码：

public class Solution{

    public List<Integer>findAnagrams(String s,String p){

        ArrayList<Integer>res=new ArrayList<>();

        if(s==null||p==null||p.length()>s.length())

            return res;

        int []map=new int [256];  //记录p中出现的元素

        for(char c:p.toCharArray())

            map[c]++;              //以c的Ascall为下标的值加一，其余没出现的都为0；

        int count=p.length(); //记录p中还未出现的字符个数

        int left=0;    //窗口左指针

        int right=0;   //窗口右指针

            while(right<s.length()){

                char ch=s.charAt(right);

                map[ch]--;

                if(map[ch]>=0)  //证明ch是p中的字符

                    count--;    //p中未出现的个数减一

                if(right-left+1==p.length()){

                    if(count==0) //说明p中的字符都已经出现

                        res.add(left);

                    char ch1=s.charAt(left);

                    map[ch1]++;

                    if(map[ch1]>0)//证明当前窗口最左边的值在p中存在，那么由于窗口要向下滑动一位，会舍弃该值，则count的数目就应该加1

                        count++;

                    left++;//窗口向下滑动

                    right++;

                }else{

                    right++;

                }

            }

        return res;

    }

}

巴特西

10.Find All Anagrams in a String（在一个字符串中发现所有的目标串排列）

Level：

题目描述：

思路分析：

代码：

最新文章

热门文章