จำนวนขั้นตอนขั้นต่ำในการสร้างแอนนาแกรมสองสตริงใน C ++

สมมติว่าเรามีสตริงที่มีขนาดเท่ากัน s และ t ในขั้นตอนเดียว เราสามารถเลือกอักขระใดก็ได้ของ t และแทนที่ด้วยอักขระอื่น เราต้องหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นในการสร้างแอนนาแกรมของ s หมายเหตุ:แอนนาแกรมของสตริงคือสตริงที่มีอักขระเดียวกันกับการเรียงลำดับที่แตกต่างกัน (หรือเหมือนกัน)

ดังนั้น หากอินพุตเป็นเช่น - "yxy" และ "xyx" เอาต์พุตจะเป็น 1 เนื่องจากจำเป็นต้องเปลี่ยนอักขระเพียงตัวเดียว

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

• n :=ขนาดของตัวอักษรใน s

• สร้างแผนที่ m และเติมด้วยความถี่ของอักขระแต่ละตัวที่มีอยู่ใน s สร้างแผนที่อื่น m2 และเติมด้วยความถี่ของอักขระแต่ละตัวที่มีอยู่ใน t

• ret :=n

• สำหรับแต่ละคีย์-ค่าจับคู่ในหน่วย m

  • x :=ค่าต่ำสุดของมัน และค่าของ m2[value of it]

  • ลดหย่อน 1

• รีเทิร์น

ตัวอย่าง (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSteps(string s, string t) {
      int n = s.size();
      map <char, int> m1;
      for(int i = 0; i < s.size(); i++){
         m1[s[i]]++;
      }
      int ret = n;
      map <char, int> m2;
      for(int i = 0; i < t.size(); i++){
         m2[t[i]]++;
      }
      map <char, int> :: iterator it = m1.begin();
      while(it != m1.end()){
         //cout << it->first << " " << it->second << " " << m2[it->first] << endl;
         int x = min(it->second, m2[it->first]);
         ret -= x;
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minSteps("yxy", "xyx"));
}

อินพุต

"yxy"
"xyx"

ผลลัพธ์

1