在C ++中制作两个字符串字谜的最小步骤数

假设我们有两个相等大小的字符串s和t。第一步,我们可以选择t的任何字符并将其替换为另一个字符。我们必须找到制作s字谜的最少步骤数。注意:字符串的Anagram是包含相同字符且具有不同(或相同)顺序的字符串。

因此,如果输入类似-“ yxy”和“ xyx”,则输出将为1,因为仅需要替换一个字符。

为了解决这个问题,我们将遵循以下步骤-

  • n:= s中字符的大小

  • 制作一个映射m,并用s中出现的每个字符的频率填充它,制作另一个映射m2,并用t中出现的每个字符的频率填充它

  • ret:= n

  • 对于每个键值对,以m为单位

    • x:=它的值的最小值,和m2 [它的值]的值

    • 将ret降低1

  • 返回ret

范例(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