假设我们有两个相等大小的字符串s和t。第一步,我们可以选择t的任何字符并将其替换为另一个字符。我们必须找到制作s字谜的最少步骤数。注意:字符串的Anagram是包含相同字符且具有不同(或相同)顺序的字符串。
因此,如果输入类似-“ yxy”和“ xyx”,则输出将为1,因为仅需要替换一个字符。
为了解决这个问题,我们将遵循以下步骤-
n:= s中字符的大小
制作一个映射m,并用s中出现的每个字符的频率填充它,制作另一个映射m2,并用t中出现的每个字符的频率填充它
ret:= n
对于每个键值对,以m为单位
x:=它的值的最小值,和m2 [它的值]的值
将ret降低1
返回ret
让我们看下面的实现以更好地理解-
#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