PythonのTの文字列Sのすべてのアナグラムの開始インデックスを見つけるプログラム

2つの文字列SとTがあるとすると、TでSのアナグラムのすべての開始インデックスを見つける必要があります。文字列は小文字のみで構成され、文字列SとTの両方の長さは20と100を超えません。

したがって、入力がS ="cab" T ="bcabxabc"のようである場合、出力は[0、1、5、]となり、部分文字列は「bca」、「cab」、「abc」になります。

これを解決するには、次の手順に従います。

• マップm、n：=sのサイズを定義し、左：=0、右：=0、カウンター：=pのサイズを設定

• 配列を定義します

• pの文字の頻度をマップmに保存します

• 右の場合：=0からn– 1

  • mにs[right]があり、m [s [right]]がゼロ以外の場合、m [s [right]]を1減らし、counterを1減らし、counter =0の場合、左をansに挿入します

  • それ以外の場合

    • 左<右

      • s [left]がmに存在しない場合は、カウンターを1増やし、m[s[left]]を1増やします

      • 左に1増加

      • mにs[right]があり、m [s [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, ]