题目描述
思路解析动画文字版
记牢这一句:扫 s 加一、扫 t 减一,最后把每个字母桶的绝对值加起来。桶里是正数代表 s 多、要补给 t,是负数代表 t 多、要补给 s,补齐都得花绝对值那么多步。下面从清空计数表开始一步步走。
先建一张计数表。两个串合起来只用到 8 种字母,l e t c o d a s,给每种字母一个桶,格子里前面是字母、后面是它当前的计数,一开始全是 0。接下来先扫 s、再扫 t,让这些数字动起来。
读到 s 的第 0 个字符是 l。找到它的桶,计数加 1,现在桶 l 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 1 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 2 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 2。e 已经是第 2 次出现了,leetcode 里有 3 个 e,这个桶会一路涨到 3。
读到 s 的第 3 个字符是 t。找到它的桶,计数加 1,现在桶 t 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 4 个字符是 c。找到它的桶,计数加 1,现在桶 c 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 5 个字符是 o。找到它的桶,计数加 1,现在桶 o 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 6 个字符是 d。找到它的桶,计数加 1,现在桶 d 里是 1。紫色高亮的就是刚刚更新的那个桶。
读到 s 的第 7 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 3。e 已经是第 3 次出现了,leetcode 里有 3 个 e,这个桶会一路涨到 3。
读到 t 的第 0 个字符是 c。给它的桶减 1,现在桶 c 里是 0。桶 c 里 s 和 t 各消掉一个,慢慢往配平的方向走。
读到 t 的第 1 个字符是 o。给它的桶减 1,现在桶 o 里是 0。桶 o 里 s 和 t 各消掉一个,慢慢往配平的方向走。
读到 t 的第 2 个字符是 a。给它的桶减 1,现在桶 a 里是 -1。注意它变成了负数,说明这个字母 t 比 s 多,记成红色,后面要把它补给 s。
读到 t 的第 3 个字符是 t。给它的桶减 1,现在桶 t 里是 0。桶 t 里 s 和 t 各消掉一个,慢慢往配平的方向走。
读到 t 的第 4 个字符是 s。给它的桶减 1,现在桶 s 里是 -1。注意它变成了负数,说明这个字母 t 比 s 多,记成红色,后面要把它补给 s。
结算字母 l 这个桶,里面是 1。是正数 1,说明 s 多出 1 个 l,要补 1 个到 t,累计步数加到 1,标红。
结算字母 e 这个桶,里面是 3。是正数 3,说明 s 多出 3 个 e,要补 3 个到 t,累计步数加到 4,标红。
结算字母 t 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
结算字母 c 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
结算字母 o 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
结算字母 d 这个桶,里面是 1。是正数 1,说明 s 多出 1 个 d,要补 1 个到 t,累计步数加到 5,标红。
结算字母 a 这个桶,里面是 -1。是负数 -1,说明 t 多出 1 个 a,要补 1 个到 s,累计步数加到 6,标红。
结算字母 s 这个桶,里面是 -1。是负数 -1,说明 t 多出 1 个 s,要补 1 个到 s,累计步数加到 7,标红。
八个桶全部结算完。绿色的 t c o 三个字母 s 和 t 里一样多,不花步数;红色的 l 有 1 个多、e 有 3 个多、d 有 1 个多,这 5 个要补到 t,a 和 s 各差 1 个要补到 s。把红色桶的绝对值加起来,1 加 3 加 1 加 1 加 1 等于 7,这就是最少步骤数。
边界想清:已是异位词记 0、完全不同字母各补一次、同字母多几个就补几个。
面试重点:计数表加减求绝对值和、允许删除答案也不变、时间线性空间常数。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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())复杂度
- 时间：O(n + m)，n 是 s 的长度、m 是 t 的长度。扫一遍 s 做加法、扫一遍 t 做减法,最后再扫固定的字母桶求和,桶只有 26 个是常数,所以整体随两个串的总长度线性增长
- 空间：O(1)，只用一张按字母计数的表。字母表固定 26 个,不随串长变化,是常数级空间;Python 的 Counter 最多也只存下 26 种小写字母,同样是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问如果改成可以删除字符,答案会变吗?
追问为什么时间是线性、空间是常数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
收集垃圾的最少总时间
LeetCode 2391 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题