You are given two strings of the same length s
and t
. In one step you can choose any character of t
and replace it with another character.
Return the minimum number of steps to make t
an anagram of s
.
An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Example 1:
Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.
Example 2:
Input: s = "leetcode", t = "practice"
Output: 5
Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.
Example 3:
Input: s = "anagram", t = "mangaar"
Output: 0
Explanation: "anagram" and "mangaar" are anagrams.
Constraints:
1 <= s.length <= 5 * 104
s.length == t.length
s
andt
consist of lowercase English letters only.
这道题给了两个字符串s和t,说是可以替换t中的字符,问最少替换多少个字符可以使得其与s是变位词。所谓的变位词,就是两个单词中字符的种类和个数均相同,就是字符的顺序不同而已。之前的题目中也做过不少关于变位词的题目,比如 Valid Anagram,Group Anagrams,Find Anagram Mappings,Find All Anagrams in a String 等等。这类题目的核心就是统计字符的出现次数,这道题也不例外,这里使用一个 HashMap 来统计字符串s中每个字符的出现次数。然后遍历字符串t,对于每个遍历到的字符,将 HashMap 中该字符的映射值自减1,这样操作之后映射值就可正可负,还可能为0。当某个映射值为正数的时候,则说明该字符在s中的数量多,若为负数,则说明该字符在t中的数量多,若为0,则说明该字符在s和t中的个数一样多。由于字符串s和t的长度相同,则正数的映射值累加和一定等于负数映射值的累加和,而且只要将所有的正数的映射字符替换成负数的映射字符,则s和t就会变成变位词,且替换次数最少,参见代码如下:
class Solution {
public:
int minSteps(string s, string t) {
int res = 0;
unordered_map<char, int> charCnt;
for (char c : s) ++charCnt[c];
for (char c : t) --charCnt[c];
for (auto a : charCnt) {
if (a.second > 0) res += abs(a.second);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1347
类似题目:
Determine if Two Strings Are Close
Minimum Number of Steps to Make Two Strings Anagram II
参考资料:
https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/
LeetCode All in One 题目讲解汇总(持续更新中...)
- 字母 LeetCode 步骤 Anagram Minimum字母leetcode步骤anagram 字母leetcode anagram valid substrings leetcode removing minimum leetcode minimum arrive speed leetcode minimum repair 2594 leetcode minimum split 2578 leetcode interval include minimum operations leetcode minimum halve leetcode minimum finish 2323 leetcode minimum penalty 2483