leetcode438. Find All Anagrams in a String

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

摘要生成于 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;
    }
};


评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值