Giả sử chúng ta có hai chuỗi có độ dài bằng nhau, chúng ta phải tìm một số thay đổi tối thiểu cần thiết để thực hiện đảo ngữ hai chuỗi mà không xóa bất kỳ ký tự nào. Anagram là hai chuỗi có cùng một bộ ký tự. Giả sử hai chuỗi là “HELLO” và “WORLD” ở đây số lượng thay đổi bắt buộc là 3, vì ba ký tự khác nhau trong trường hợp này.
Ý tưởng rất đơn giản, chúng ta phải tìm tần số của từng ký tự trong chuỗi đầu tiên, sau đó chuyển qua chuỗi thứ hai, nếu các ký tự trong chuỗi thứ hai có mặt, trong mảng tần số, sau đó giảm giá trị tần số. Nếu giá trị tần suất nhỏ hơn 0, thì hãy tăng số lượng cuối cùng lên 1.
Ví dụ
#include <iostream>
using namespace std;
int countAlteration(string str1, string str2) {
int count = 0;
int frequency[26];
for (int i = 0; i < 26; i++){
frequency[i] = 0;
}
for (int i = 0; i < str1.length(); i++)
frequency[str1[i] - 'A']++;
for (int i = 0; i < str2.length(); i++){
frequency[str2[i] - 'A']--;
if (frequency[str2[i] - 'A'] < 0)
count++;
}
return count;
}
int main() {
string s1 = "HELLO", s2 = "WORLD";
cout << "Number of required alteration: " << countAlteration(s1, s2);
} Đầu ra
Number of required alteration: 3