Leetcode——438. Find All Anagrams in a String

本文主要是介绍Leetcode——438. Find All Anagrams in a String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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”.

解答

使用unordered_map

class Solution1 {//超时
public:vector<int> findAnagrams(string s, string p) {vector<int> res;if(s.length()<p.length()) return res;unordered_map<char,int> mp;for(int i=0;i<p.length();i++){mp[p[i]]++;}for(int i=0;i<=s.length()-p.length();i++)//遍历每一个元素{unordered_map<char,int> m;for(int j=i;j-i<p.length();j++)//每次都更新p.length()个（这个增加了时间消耗）{m[s[j]]++;}unordered_map<char,int>::iterator itr;for(itr=mp.begin();itr!=mp.end();itr++)//遍历mp中元素个数是否和m中元素个数相等，因为总数是相等的，所以两者只要有一个不一样，都会break，这里遍历mp和遍历m效果是一样的。{if(m[itr->first]==mp[itr->first]) continue;elsebreak;}if(itr==mp.end()) res.push_back(i);//两者都一样，才能加入}return res;}
};

上述方法比较耗费时间！时间复杂度是O(N*K)

可以改进上述方法
思想也是维持一个滑动的窗，不过这个窗在循环外面先初始化好，进入循环后，每次更新两个元素，即在窗首添加一个元素，在窗尾去除一个元素。

class Solution2 {//没超时，不过时间也很长(17%)
public:vector<int> findAnagrams(string s, string p) {vector<int> res;if(s.length()<p.length()) return res;unordered_map<char,int> mp;unordered_map<char,int> ms;for(int i=0;i<p.length();i++){mp[p[i]]++;ms[s[i]]++;}int i=0;do{unordered_map<char,int>::iterator itr;for(itr=mp.begin();itr!=mp.end();itr++){if(mp[itr->first]==ms[itr->first]) continue;elsebreak;}if(itr==mp.end()) res.push_back(i);ms[s[i+p.length()]]++;ms[s[i]]--;i++;}while(i+p.length()<s.length());unordered_map<char,int>::iterator itr;for(itr=mp.begin();itr!=mp.end();itr++){if(mp[itr->first]==ms[itr->first]) continue;elsebreak;}if(itr==mp.end()) res.push_back(i);return res;}
};

使用滑动窗！Sliding window!
使用一个数组，来维持，数组长度为26。85%
33ms。

class Solution {//没超时，时间太长
public:vector<int> findAnagrams(string s, string p) {vector<int> res;if(s.length()<p.length()||p.length()==0) return res;int mp[26]={0};int ms[26]={0};for(int i=0;i<p.length();i++){mp[p[i]-'a']++;ms[s[i]-'a']++;}if(isequal(mp,ms,26))res.push_back(0);for(int i=p.length();i<s.length();i++)//滑动窗{ms[s[i]-'a']++;ms[s[i-p.length()]-'a']--;if(isequal(mp,ms,26))res.push_back(i-p.length()+1);}return res;}
private:bool isequal(int a[],int b[],int n){for(int i=0;i<n;i++)if(a[i]!=b[i])return false;return true;}
};