数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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"
输出
1
更新于: 2020-04-29
216 次查看
广告