leetcode438. Find All Anagrams in a String

最新推荐文章于 2025-05-18 16:01:12 发布

Coding_Reading

最新推荐文章于 2025-05-18 16:01:12 发布

阅读量571

点赞数

分类专栏： LeetCode

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/52959394

版权

LeetCode 专栏收录该内容

32 篇文章

订阅专栏

本文介绍了一种高效算法来查找一个字符串中所有给定单词的字母异位词的位置。通过使用滑动窗口和计数数组的方法，避免了传统方法中的超时问题，实现了快速匹配。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1.题目

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 s and 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".

2.想法

先写出来的暴力无脑方式，将p进行sort()升序，然后创建数组temp,将p.length()个字符拷入temp中，对temp运用sort(),再strcmp()两个字符串,

结果毫无疑问的运行超时！

参考别人解法后，得到思路。

用数组count存贮p字符串字符个数分布情况，

然后“滑动”S中连续的p.length()个字符，用temp数组存储S中p.length()个字符个数分布，依次往后递进，每递进一次与count比较一次。

3.AC解

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> result;
        const int N=p.length();
        if(s.length()<N)
            return result;
            
        int* count=new int [26];
        for(int i=0;i<26;i++)
            count[i]=0;
            
        int* temp=new int [26];
        for(int i=0;i<26;i++)
            temp[i]=0;
            
        for(char a:p)
            count[a-'a']++;
        
        for(int i=0;i<N;i++)
            temp[s[i]-'a']++;
        if(cmp(temp,count,26))
            result.push_back(0);
            
        for(int i=N;i<s.length();i++)
        {
            temp[s[i-N]-'a']--;//删去前面的一个
            temp[s[i]-'a']++;//加上后面的一个
            if(cmp(temp,count,26))
                result.push_back(i-N+1);
        }
        
        return result;
            
    }
    
    bool cmp(int *p1, int* p2,int N)
    {
        while(N--)
        {
            if(p1[N]!=p2[N])
                return false;
        }
        
        return true;
    }
};