题目描述
思路解析动画文字版
记牢这一句:f[i] 只有两种来路,要么让第 i 个字符当额外字符,在 f[i-1] 上加一;要么发现有单词正好在这里结尾,直接接上那个单词开头前的 f[j]。两者取最小。下面从 f[0] 开始一格一格填。
初始化 · f[0] = 0：先看最左边一列,列头是 0,表示只看前 0 个字符,也就是空串。空串里一个字符都没有,自然没有额外字符,所以 f[0] 直接定成 0。这一格是整张表的地基,后面每个 f 值都要从它一步步接出来。上行是 s 的五个字符 c o d e x,列头 1 到 5 对应看前几个字符。
看前 1 个字符 · 先假设 c 是额外字符：现在算 f[1],看前 1 个字符。第一手最保守:假设第 1 个字符 c 谁都用不上,是个额外字符。那就在前 0 个字符的最优解 f[0] 等于 0 上再加一个额外字符,f[1] 先暂定为 1。这只是保底值,接下来看能不能靠单词把它压得更小。
子串 "c" 不在字典 · 跳过：把起点放在第 0 列,取出这一段 "c"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[1] 还是 1。继续把起点往右挪,试下一段。
看前 2 个字符 · 先假设 o 是额外字符：现在算 f[2],看前 2 个字符。第一手最保守:假设第 2 个字符 o 谁都用不上,是个额外字符。那就在前 1 个字符的最优解 f[1] 等于 1 上再加一个额外字符,f[2] 先暂定为 2。这只是保底值,接下来看能不能靠单词把它压得更小。
子串 "co" 不在字典 · 跳过：把起点放在第 0 列,取出这一段 "co"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[2] 还是 2。继续把起点往右挪,试下一段。
子串 "o" 不在字典 · 跳过：把起点放在第 1 列,取出这一段 "o"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[2] 还是 2。继续把起点往右挪,试下一段。
看前 3 个字符 · 先假设 d 是额外字符：现在算 f[3],看前 3 个字符。第一手最保守:假设第 3 个字符 d 谁都用不上,是个额外字符。那就在前 2 个字符的最优解 f[2] 等于 2 上再加一个额外字符,f[3] 先暂定为 3。这只是保底值,接下来看能不能靠单词把它压得更小。
子串 "cod" 不在字典 · 跳过：把起点放在第 0 列,取出这一段 "cod"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
子串 "od" 不在字典 · 跳过：把起点放在第 1 列,取出这一段 "od"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
子串 "d" 不在字典 · 跳过：把起点放在第 2 列,取出这一段 "d"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
看前 4 个字符 · 先假设 e 是额外字符：现在算 f[4],看前 4 个字符。第一手最保守:假设第 4 个字符 e 谁都用不上,是个额外字符。那就在前 3 个字符的最优解 f[3] 等于 3 上再加一个额外字符,f[4] 先暂定为 4。这只是保底值,接下来看能不能靠单词把它压得更小。
子串 "code" 命中 · f[4] 更新为 0：把起点往回挪到第 0 列,取出这一段子串 "code"。它正好是字典里的单词,这一段零额外字符。于是可以把它接在 f[0] 等于 0 后面,得到 0。这个值比刚才的暂定值更小,f[4] 就被压到 0,两端和这段字符一起染绿表示命中。
子串 "ode" 也是单词 · 但不更优：再把起点挪到第 1 列,这段 "ode" 也是字典里的单词。不过接上 f[1] 等于 1 的结果并不比当前的 f[4] 等于 0 更小,所以取最小值时它落选,f[4] 保持 0。命中不等于一定采纳,还要看谁的 f 更小。
子串 "de" 不在字典 · 跳过：把起点放在第 2 列,取出这一段 "de"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[4] 还是 0。继续把起点往右挪,试下一段。
子串 "e" 不在字典 · 跳过：把起点放在第 3 列,取出这一段 "e"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[4] 还是 0。继续把起点往右挪,试下一段。
看前 5 个字符 · 先假设 x 是额外字符：现在算 f[5],看前 5 个字符。第一手最保守:假设第 5 个字符 x 谁都用不上,是个额外字符。那就在前 4 个字符的最优解 f[4] 等于 0 上再加一个额外字符,f[5] 先暂定为 1。这只是保底值,接下来看能不能靠单词把它压得更小。
子串 "codex" 不在字典 · 跳过：把起点放在第 0 列,取出这一段 "codex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
子串 "odex" 不在字典 · 跳过：把起点放在第 1 列,取出这一段 "odex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
子串 "dex" 不在字典 · 跳过：把起点放在第 2 列,取出这一段 "dex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
子串 "ex" 不在字典 · 跳过：把起点放在第 3 列,取出这一段 "ex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
子串 "x" 不在字典 · 跳过：把起点放在第 4 列,取出这一段 "x"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
读出答案 · f[5] = 1：整张表填满,最后一列 f[5] 就是答案。它等于 1,意思是把 codex 最优分割后只剩 1 个额外字符。回头看这条最优路线:code 从第 0 位接到第 4 位这一段是单词、零额外,末尾那个 x 谁也覆盖不了,是唯一的额外字符,正好 1 个。
边界想清:整串恰是单词记 0、无单词可用则全是额外、只能覆盖一部分时剩下的就是额外字符数。
面试重点:f[i] 双转移取最小、字典树可把枚举优化到 O(n 平方)、贪心会错必须用动态规划。
参考代码
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 minExtraChar(self, s: str, dictionary: List[str]) -> int: ss = set(dictionary) n = len(s) f = [0] * (n + 1) for i in range(1, n + 1): f[i] = f[i - 1] + 1 for j in range(i): if s[j:i] in ss and f[j] < f[i]: f[i] = f[j] return f[n]复杂度
- 时间：O(n² · L)，n 是 s 的长度。外层 i 走 n 步,内层 j 又到 n 步,一共约 n 的平方对 (i,j);每一对都要截出子串再丢进哈希集合比对,子串长度最长到 L,截取加哈希是 O(L)。所以是 O(n 的平方乘 L),最坏可看作 O(n 的三次方)。用字典树把「以 i 结尾的单词」查询优化后可降到 O(n 的平方)
- 空间：O(n + M)，按峰值算。f 数组占 O(n);字典哈希集合把所有单词存下来,占 O(M),M 是字典里全部单词的总字符数。两者相加,不随 n 平方增长
易错点
面试追问把动画讲成自己的话
追问这题的状态和转移怎么定义?
追问朴素做法慢在哪,怎么优化?
追问为什么用动态规划而不是贪心?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
正则表达式匹配
LeetCode 10 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题