Giả sử chúng ta có hai chuỗi có kích thước bằng nhau s và t. Trong một bước, chúng ta có thể chọn bất kỳ ký tự nào của t và thay thế nó bằng một ký tự khác. Chúng ta phải tìm số bước tối thiểu cần thiết để biến t trở thành một chữ cái đảo chữ của s. Lưu ý:Đảo chữ cái của một chuỗi là một chuỗi chứa các ký tự giống nhau với thứ tự khác nhau (hoặc giống nhau).
Vì vậy, nếu đầu vào là - “yxy” và “xyx”, thì đầu ra sẽ là 1, vì chỉ cần một ký tự được thay thế.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
-
n:=kích thước ký tự tính bằng s
-
tạo một bản đồ m và điền vào bản đồ này với tần suất của mỗi ký tự hiện diện trong s, tạo một bản đồ khác m2 và điền vào bản đồ này với tần suất của mỗi ký tự hiện diện trong t
-
ret:=n
-
đối với mỗi khóa-giá trị, hãy ghép nối nó bằng m
-
x:=giá trị nhỏ nhất của nó và giá trị của m2 [giá trị của nó]
-
giảm ret xuống 1
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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"));
} Đầu vào
"yxy" "xyx"
Đầu ra
1