โปรแกรมค้นหาดัชนีเริ่มต้นของแอนนาแกรมทั้งหมดของสตริง S ใน T ใน Python

สมมติว่าเรามีสตริง S และ T สองสตริง เราต้องหาดัชนีเริ่มต้นทั้งหมดของแอนนาแกรมของ S ใน T สตริงประกอบด้วยตัวอักษรตัวพิมพ์เล็กเท่านั้น และความยาวของทั้งสองสตริง S และ T จะไม่เกิน 20 และ 100

ดังนั้น หากอินพุตเป็นเหมือน S ="cab" T ="bcabxabc" เอาต์พุตจะเป็น [0, 1, 5, ] เป็นสตริงย่อย "bca", "cab" และ "abc"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• กำหนดแผนที่ m, n :=size of s, set left :=0, right :=0, counter :=size of p

• กำหนดอาร์เรย์และ

• เก็บความถี่ของตัวอักษรใน p ลงในแผนที่ m

• ขวา :=0 ถึง n – 1

  • ถ้า m มี s[right] และ m[s[right]] ไม่ใช่ศูนย์ ให้ลดค่า m[s[right]] ลง 1 ให้ลดตัวนับลง 1 และถ้าตัวนับ =0 ให้ใส่ left ใน ans

  • อย่างอื่น

    • ขณะที่ซ้าย <ขวา

      • ถ้า s[left] ไม่มีอยู่ใน m ให้เพิ่มตัวนับขึ้น 1 และเพิ่ม m[s[left]] ขึ้น 1

      • เพิ่มขึ้น 1

      • ถ้า m มี s[right] และ m[s[right]] ไม่ใช่ศูนย์ ให้ลดลงทางขวา 1 แล้วออกจากลูป

    • ถ้า m ไม่มี s[left] ให้ตั้งค่า left :=right + 1

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

#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, ]