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

标签: 哈希表 字符串 计数

难度: Medium

给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。

返回使 s 和 t 互为 字母异位词 所需的最少步骤数。

字母异位词 指字母相同但是顺序不同（或者相同）的字符串。

示例 1：

输入：s = "leetcode", t = "coats"
输出：7
解释：
- 执行 2 步操作，将 "as" 追加到 s = "leetcode" 中，得到 s = "leetcodeas" 。
- 执行 5 步操作，将 "leede" 追加到 t = "coats" 中，得到 t = "coatsleede" 。
"leetcodeas" 和 "coatsleede" 互为字母异位词。
总共用去 2 + 5 = 7 步。
可以证明，无法用少于 7 步操作使这两个字符串互为字母异位词。

示例 2：

输入：s = "night", t = "thing"
输出：0
解释：给出的字符串已经互为字母异位词。因此，不需要任何进一步操作。

提示：

  • 1 <= s.length, t.length <= 2 * 105
  • s 和 t 由小写英文字符组成

Submission

运行时间: 166 ms

内存: 17.3 MB

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt1 = Counter(s)
        cnt2 = Counter(t)
        cnt = cnt1 + cnt2
        ans = 0
        for k, v in cnt.items():
            ans += abs(v - 2 * cnt1[k])
        # print(cnt)
        return ans

Explain

本题解采用计数字典来记录两个字符串中每个字符的出现次数。首先，使用Counter对字符串s和t进行计数获取cnt1和cnt2。然后，通过将cnt1和cnt2相加，得到一个新的计数字典cnt，其中的值是字符在s和t中出现的总次数。接着，遍历cnt字典的每个键值对，计算每个字符在s中应有的数量（即总数的一半，这样才能使s和t的该字符数量相等），通过累加每个字符的差的绝对值来计算需要添加的字符总数。

时间复杂度: O(n + m)

空间复杂度: O(u)

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        from collections import Counter
        # 计数s和t中的每个字符
        cnt1 = Counter(s)
        cnt2 = Counter(t)
        # 将两个计数器相加得到总计数
        cnt = cnt1 + cnt2
        ans = 0
        # 遍历每个字符，计算使s和t成为字母异位词的最小步骤数
        for k, v in cnt.items():
            ans += abs(v - 2 * cnt1[k])
        return ans

Explore

Counter 是 Python collections 模块中的一个特殊的字典类，专门用于计数可哈希对象。它提供了直观的函数和操作来计数元素的频率，如自动计数和合并计数。使用 Counter 可以简化代码，并且比手动使用普通字典更高效，因为它内部优化了计数逻辑。此外，Counter 支持直接的数学运算，如加法和减法，这在处理两个字符串中字符的总出现次数时非常有用。因此，选择 Counter 是因为它的便捷性和对问题场景的直接支持。

此计算公式基于使两个字符串 s 和 t 的每个字符数量相等的目标。变量 `v` 代表字符 k 在 s 和 t 中总共出现的次数，而 `2 * cnt1[k]` 是字符 k 在 s 中应出现的两倍计数。这个差的绝对值 `abs(v - 2 * cnt1[k])` 表示 s 需要增加或减少多少个字符 k 来使其数量达到总数的一半，从而与 t 中的数量相匹配。这确保了在最终的 s 和 t 中，每个字符的数量是相等的，满足字母异位词的条件。

将 cnt1 和 cnt2 相加的目的是得到一个包含所有字符的总计数，这简化了比较和计算过程。通过这种方式，我们可以直接计算出每个字符应在两个字符串中平均出现的次数（即总数的一半）。这使得可以一步计算出两个字符串中每个字符的目标数量，进而直接计算出需要添加或减少的字符数量。总的来说，这种方法提高了效率和代码的清晰度，避免了繁琐的单独处理每个字符串的步骤。