C++ 中将两个字符串变成字谜的最小步数


假设我们有两个大小相同的字符串 s 和 t。在一步操作中,我们可以选择 t 的任何字符并将其替换为另一个字符。我们需要找到使 t 成为 s 的字谜所需的最小步数。注意:字符串的字谜是指包含相同字符但顺序不同(或相同)的字符串。

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

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

  • n := s 中字符的大小

  • 创建一个映射 m,并用 s 中存在的每个字符的频率填充它,创建一个映射 m2,并用 t 中存在的每个字符的频率填充它

  • ret := n

  • 对于 m 中的每个键值对 it

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

    • 将 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"

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

1

更新于: 2020-04-29

216 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告