制造字母异位词的最小步骤数

标签: 哈希表 字符串 计数

难度: Medium

给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。

返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词 指字母相同，但排列不同（也可能相同）的字符串。

示例 1：

输出：s = "bab", t = "aba"
输出：1
提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。

示例 2：

输出：s = "leetcode", t = "practice"
输出：5
提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。

示例 3：

输出：s = "anagram", t = "mangaar"
输出：0
提示："anagram" 和 "mangaar" 本身就是一组字母异位词。

示例 4：

输出：s = "xxyyzz", t = "xxyyzz"
输出：0

示例 5：

输出：s = "friend", t = "family"
输出：4

提示：

  • 1 <= s.length <= 50000
  • s.length == t.length
  • s 和 t 只包含小写英文字母

Submission

运行时间: 88 ms

内存: 0.0 MB

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        countS = Counter(s)
        countT = Counter(t)
        ans = 0
        for key in (set(countS.keys()) | set(countT.keys())):
            if countS[key] < countT[key]:
                ans += countT[key] - countS[key]
        return ans

Explain

此题解的思路是首先统计两个字符串s和t中每个字符的出现次数，然后比较两个统计结果。对于t中每个字符的出现次数如果超过了s中相应字符的出现次数，就需要进行替换，替换的次数等于t中该字符的出现次数与s中该字符出现次数的差值。最终将所有需要替换的次数累加起来即可得到答案。

时间复杂度: O(n)

空间复杂度: O(C)

from collections import Counter

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        countS = Counter(s)  # 统计字符串s中各字符的出现次数
        countT = Counter(t)  # 统计字符串t中各字符的出现次数
        ans = 0  # 初始化答案变量
        # 遍历s和t中出现的所有字符
        for key in (set(countS.keys()) | set(countT.keys())):
            if countS[key] < countT[key]:  # 如果t中字符出现次数超过s中的
                ans += countT[key] - countS[key]  # 增加差值到答案中
        return ans  # 返回最终答案

Explore

Counter类是Python中collections模块提供的一个特殊的字典子类，专门用于计数可哈希对象。它在处理字符频率统计时具有几个优势：1. 自动初始化：Counter在遇到新键时会自动将计数初始化为0，避免了手动检查和更新不存在的键的需求。2. 提供额外功能：例如most_common方法可以快速返回出现次数最多的元素列表。3. 代码简洁：使用Counter可以使代码更加简洁易读，减少编码错误。总之，Counter提供了更高效、便捷的方式来处理频率统计任务。

使用`set(countS.keys()) | set(countT.keys())`可以确保遍历s和t字符串中所有出现过的字符，即使某字符在一个字符串中出现而在另一个中没有出现。这样做是为了全面计算必要的字符替换次数，因为可能存在某个字符在s中有而在t中没有，或者在t中有而在s中没有的情况，这些情况都需要计算到最终的替换步数中。如果只遍历s或t中的字符，可能会遗漏对方字符串特有的字符，导致计算错误。

如果s中的字符出现次数超过t中相应字符的出现次数，实际上这并不影响最小替换步骤的计算。因为题目的目标是使t变成s的字母异位词，只关注t中需要减少或替换掉的字符数量。s中字符频率超过t仅意味着t需要增加某些字符的频率，这可以通过减少t中其他过量字符的频率来实现，而不需要额外操作。因此，只考虑t中字符出现次数超过s的情况，是因为这直接关系到将t中字符替换为s中字符的步数。