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

发表于 阅读次数：

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result=new ArrayList();
        int pLen=p.length();
        int sLen=s.length();
        String pSort=strSort(p);
        for(int i=0;i+pLen<=sLen;i++)
        {
            if(pSort.equals(strSort(s.substring(i,i+pLen))))
            {
                result.add(i);
            }
        }
        return result;
    }
    public String strSort(String str)
    {
        char[] ch=str.toCharArray();
        Arrays.sort(ch);
        return String.valueOf(ch);
    }
}

思路为将s的子串和p重新排序输出字符串，然后让s的子串向左滑动，求出满足异位词条件的索引。

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> ans=new ArrayList<Integer>();

    int sLen=s.length();
    int pLen=p.length();

    if(sLen<pLen){
        return ans;
    }
    //建立两个数组存放字符串中字母出现的词频，并以此作为标准比较
    int [] scount=new int[26];
    int [] pcount=new int[26];

    //当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）
    for(int i=0;i<pLen;i++){
        ++scount[s.charAt(i)-'a']; //记录s中前pLen个字母的词频
        ++pcount[p.charAt(i)-'a']; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
    }

    //判断放置处是否有异位词     (在放置时只需判断一次)
    if(Arrays.equals(scount,pcount)){
         ans.add(0);
    }   

    //开始让窗口进行滑动
    for(int i=0;i<sLen-pLen;i++){ //i是滑动前的首位
        --scount[s.charAt(i) -'a'];       //将滑动前首位的词频删去
        ++scount[s.charAt(i+pLen) -'a'];  //增加滑动后最后一位的词频（以此达到滑动的效果）

        //判断滑动后处，是否有异位词
        if(Arrays.equals(scount,pcount)){
            ans.add(i+1);
        } 
    }

    return ans;
}
}

https://leetcode.cn/problems/find-all-anagrams-in-a-string/solution/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/
该网址的评论区。

思路大致也是滑动窗口，但是比较字符串是不是异位词和我的不一样，该方法比较异位词是将s的子串和p的字母放到了数组中，通过比较p和s的子串的数组中字母的频数一不一样来判断是否是异位词，通过–scount和++scount来控制窗口的滑动。