AlgoPressAppearance
0438-找到字符串中所有字母异位词
题目描述
https://leetcode.cn/problems/find-all-anagrams-in-a-string
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
- 1 <= s.length, p.length <= 3 * 10^4
- s 和 p 仅包含小写字母
思路：暴力比较，会超时
将目标串 p 排序后作为临时变量，将 s 遍历到 s.Length - p.Length，每次截取字符串排序后判断是否相等，相等则输出结果。
csharp
public class Solution {
private string SortString(string input){
char[] arr = input.ToCharArray();
Array.Sort(arr);
return new string(arr);
}
public IList<int> FindAnagrams(string s, string p) {
List<int> result = new List<int>();
if(s == null || p == null || p.Length == 0){
return result;
}
string key = SortString(p);
for(int i=0; i<=s.Length - p.Length; i++){
if(SortString(s.Substring(i,p.Length)) == key){
result.Add(i);
}
}
return result;
}
}
思路2：哈希表
统计滑动窗口中的字符个数，使用hash表储存 注意加入 result 的时候，要计算正确的位置 i - p.Length + 1
注意：异位词的长度是一样的，所以窗口也是等长的
csharp
public class Solution {
private bool Contains(Dictionary<char,int> dict1, Dictionary<char,int> dict2){
foreach(char c in dict2.Keys){
if(!dict1.ContainsKey(c) || dict1[c] < dict2[c]){
return false;
}
}
return true;
}
private void AddDict(Dictionary<char,int> dict, char key){
if(!dict.ContainsKey(key)){
dict.Add(key,1);
}
else{
dict[key]++;
}
}
public IList<int> FindAnagrams(string s, string p) {
List<int> result = new List<int>();
if(s == null || p == null || s.Length < p.Length){
return result;
}
Dictionary<char,int> dictSource = new Dictionary<char,int>();
Dictionary<char,int> dictTarget = new Dictionary<char,int>();
for(int i=0; i<p.Length; i++){
AddDict(dictSource,s[i]);
AddDict(dictTarget,p[i]);
}
if(Contains(dictSource,dictTarget)){
result.Add(0);
}
for(int i=p.Length; i<s.Length; i++){
AddDict(dictSource,s[i]); //添加一个新字符
dictSource[s[i-p.Length]]--; //移除一个旧字符
if(Contains(dictSource,dictTarget)){
result.Add(i-p.Length+1);
}
}
return result;
}
}
思路3：滑动窗口(right消耗字符,left增加字符)
csharp
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int[] cnt = new int[128];
int left = 0 , right = 0;
List<int> result = new List<int>();
//将目标串的个数加入 cnt
for(int i=0; i<p.Length; i++){
cnt[p[i]]++;
}
while(right < s.Length){
if(cnt[s[right]] > 0){
cnt[s[right]]--;
right++;
if(right - left == p.Length){
result.Add(left);
}
}
else{
cnt[s[left]]++;
left++;
}
}
return result;
}
}
复习滑动窗口
csharp
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
//滑动窗口
char[] arr = new char[128]; //字符数组缓存
for(int i=0; i<p.Length; i++){
arr[p[i]]++; //统计目标字符个数
}
int left = 0, right = 0;
List<int> result = new List<int>();
while(right < s.Length){
if(arr[s[right]] > 0){ //有这个字符，就消耗
arr[s[right]]--;
right++;
if(right - left == p.Length){ //如果此时长度满足，说明刚好消耗掉 p 中的字符
result.Add(left);
}
}
else{ // 左指针把消耗字符加回来
arr[s[left]]++;
left++;
}
}
return result;
}
}
复习滑动窗口：20220603
首先把目标字符串加进去，当指针处开始消耗的时候如果发现长度就等于p的长度，说明正好消耗完，是 异位词。 当不能消耗的时候，会不停的左字符加进去，然后右指针消耗，直到 下次一满足条件。 比如 目标字符是 abc, 源字符是 dddabc ，那么第一次没有消耗， left 把 d 加进去 d=1 然后 right 就把他消耗掉 d=0, 然后继续加和减。 直到 left = 3, a 的地方， right 可以消耗已经原有的字符 abc ，满足条件后计算出index=3，加入结果集.
如果源字符是 dddabxxxbac 那么在 ab 消耗掉两个字符，到x不满足， left 指针移动的时候，会把a,b重新加回来
csharp
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
//定义 char 数组
int[] chars = new int[128];
for(int i=0; i<p.Length; i++){
chars[p[i]]++;
//Console.WriteLine("chars[{0}]={1}",p[i],chars[p[i]]);
}
List<int> result = new List<int>();
int left = 0 ;
int right = 0;
while(right < s.Length){
if(chars[s[right]] > 0){
chars[s[right]]--;
if(right - left + 1 == p.Length){
result.Add(left);
}
right++;
}
else{
chars[s[left]]++;
left++;
}
}
return result;
}
}