LeetCode 题解工作台
制造字母异位词的最小步骤数 II
给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。 返回使 s 和 t 互为 字母异位词 所需的最少步骤数 。 字母异位词 指字母相同但是顺序不同（或者相同）的字符串。 示例 1： 输入： s = " lee t co de ", t = "co a t s " …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
class Solution: def minSteps(self, s: str, t: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你两个字符串 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 * 105s和t由小写英文字符组成
解题思路
方法一：计数
class Solution:
def minSteps(self, s: str, t: str) -> int:
cnt = Counter(s)
for c in t:
cnt[c] -= 1
return sum(abs(v) for v in cnt.values())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m) where n and m are the lengths of s and t, as we traverse both strings once and iterate over at most 26 characters. Space complexity is O(1) because the hash table only stores counts for lowercase letters, a fixed size of 26. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Counts mismatch between s and t indicates hash table usage.
- question_mark
Ask for O(n) approach rather than sorting the strings.
- question_mark
Check handling of strings already anagrams, expecting zero steps.
常见陷阱
外企场景- error
Forgetting to take absolute differences, causing negative step counts.
- error
Using sorting instead of counting, which increases time complexity unnecessarily.
- error
Not accounting for characters missing in one string, leading to undercounted steps.
进阶变体
外企场景- arrow_right_alt
Instead of appending, compute deletions to achieve anagrams.
- arrow_right_alt
Allow only one string to be modified to match the other as an anagram.
- arrow_right_alt
Extend to Unicode characters instead of just lowercase English letters.