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
广告