Python程序：查找字符串T中字符串S所有异位词的起始索引

假设我们有两个字符串S和T，我们需要找到S的所有异位词在T中的所有起始索引。字符串只包含小写字母，并且字符串S和T的长度都不会超过20和100。

因此，如果输入类似于S = "cab" T = "bcabxabc"，则输出将为[0, 1, 5]，因为子字符串"bca"、"cab"和"abc"。

为了解决这个问题，我们将遵循以下步骤

• 定义一个映射m，n := s的长度，设置left := 0，right := 0，counter := p的长度

• 定义一个数组ans

• 将p中字符的频率存储到映射m中

• 对于right := 0 到 n – 1

  • 如果m包含s[right]且m[s[right]]不为零，则将m[s[right]]减少1，将counter减少1，如果counter = 0，则将left插入ans

  • 否则

    • 当left < right时，

      • 如果m中不存在s[left]，则将counter增加1，并将m[s[left]]增加1

      • 将left增加1

      • 如果m包含s[right]且m[s[right]]不为零，则将right减少1，并退出循环

    • 如果m不包含s[left]，则设置left := right + 1

• 返回ans

让我们看看下面的实现以更好地理解

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findAnagrams(string s, string p) {
      map <char, int> m;
      int n = s.size();
      int left = 0, right = 0;
      int counter = p.size();
      vector <int> ans;
      for(int i = 0; i < p.size(); i++) m[p[i]]++;
      for(int right = 0; right < n; right++){
         if(m.find(s[right]) != m.end() && m[s[right]]){
            m[s[right]]--;
            counter--;
            if(counter == 0)ans.push_back(left);
         } else {
            while(left<right){
               if(m.find(s[left]) != m.end()) {
                  counter++;
                  m[s[left]]++;
               }
               left++;
               if(m.find(s[right]) != m.end() && m[s[right]]){
                  right--;
                  break;
               }
            }
            if(m.find(s[left])==m.end())left = right + 1;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.findAnagrams("bcabxabc", "cab")) ;
}

输入

"bcabxabc", "cab"

输出

[0, 1, 5, ]

Arnab Chakraborty

更新于: 2020年11月9日

157 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习