字符串中的额外字符 图解题解
这道题到底在问什么
- 输入
- s = "leetscode", dictionary = ["leet","code","leetcode"]
- 输出
- 1
- 输入
- s = "sayhelloworld", dictionary = ["hello","world"]
- 输出
- 3
最优解：一步一步想明白
- 3记牢这一句:f[i] 只有两种来路,要么让第 i 个字符当额外字符,在 f[i-1] 上加一;要么发现有单词正好在这里结尾,直接接上那个单词开头前的 f[j]。两者取最小。下面从 f[0] 开始一格一格填。
- 4地基:f[0]=0先看最左边一列,列头是 0,表示只看前 0 个字符,也就是空串。空串里一个字符都没有,自然没有额外字符,所以 f[0] 直接定成 0。这一格是整张表的地基,后面每个 f 值都要从它一步步接出来。上行是 s 的五个字符 c o d e x,列头 1 到 5 对应看前几个字符。
- 5前 1 位 · 暂定 1现在算 f[1],看前 1 个字符。第一手最保守:假设第 1 个字符 c 谁都用不上,是个额外字符。那就在前 0 个字符的最优解 f[0] 等于 0 上再加一个额外字符,f[1] 先暂定为 1。这只是保底值,接下来看能不能靠单词把它压得更小。
- 6不是单词,跳过把起点放在第 0 列,取出这一段 "c"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[1] 还是 1。继续把起点往右挪,试下一段。
- 7前 2 位 · 暂定 2现在算 f[2],看前 2 个字符。第一手最保守:假设第 2 个字符 o 谁都用不上,是个额外字符。那就在前 1 个字符的最优解 f[1] 等于 1 上再加一个额外字符,f[2] 先暂定为 2。这只是保底值,接下来看能不能靠单词把它压得更小。
- 8不是单词,跳过把起点放在第 0 列,取出这一段 "co"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[2] 还是 2。继续把起点往右挪,试下一段。
- 9不是单词,跳过把起点放在第 1 列,取出这一段 "o"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[2] 还是 2。继续把起点往右挪,试下一段。
- 10前 3 位 · 暂定 3现在算 f[3],看前 3 个字符。第一手最保守:假设第 3 个字符 d 谁都用不上,是个额外字符。那就在前 2 个字符的最优解 f[2] 等于 2 上再加一个额外字符,f[3] 先暂定为 3。这只是保底值,接下来看能不能靠单词把它压得更小。
- 11不是单词,跳过把起点放在第 0 列,取出这一段 "cod"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
- 12不是单词,跳过把起点放在第 1 列,取出这一段 "od"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
- 13不是单词,跳过把起点放在第 2 列,取出这一段 "d"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[3] 还是 3。继续把起点往右挪,试下一段。
- 14前 4 位 · 暂定 4现在算 f[4],看前 4 个字符。第一手最保守:假设第 4 个字符 e 谁都用不上,是个额外字符。那就在前 3 个字符的最优解 f[3] 等于 3 上再加一个额外字符,f[4] 先暂定为 4。这只是保底值,接下来看能不能靠单词把它压得更小。
- 15命中,压到 0把起点往回挪到第 0 列,取出这一段子串 "code"。它正好是字典里的单词,这一段零额外字符。于是可以把它接在 f[0] 等于 0 后面,得到 0。这个值比刚才的暂定值更小,f[4] 就被压到 0,两端和这段字符一起染绿表示命中。
- 16命中但落选再把起点挪到第 1 列,这段 "ode" 也是字典里的单词。不过接上 f[1] 等于 1 的结果并不比当前的 f[4] 等于 0 更小,所以取最小值时它落选,f[4] 保持 0。命中不等于一定采纳,还要看谁的 f 更小。
- 17不是单词,跳过把起点放在第 2 列,取出这一段 "de"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[4] 还是 0。继续把起点往右挪,试下一段。
- 18不是单词,跳过把起点放在第 3 列,取出这一段 "e"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[4] 还是 0。继续把起点往右挪,试下一段。
- 19前 5 位 · 暂定 1现在算 f[5],看前 5 个字符。第一手最保守:假设第 5 个字符 x 谁都用不上,是个额外字符。那就在前 4 个字符的最优解 f[4] 等于 0 上再加一个额外字符,f[5] 先暂定为 1。这只是保底值,接下来看能不能靠单词把它压得更小。
- 20不是单词,跳过把起点放在第 0 列,取出这一段 "codex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
- 21不是单词,跳过把起点放在第 1 列,取出这一段 "odex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
- 22不是单词,跳过把起点放在第 2 列,取出这一段 "dex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
- 23不是单词,跳过把起点放在第 3 列,取出这一段 "ex"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
- 24不是单词,跳过把起点放在第 4 列,取出这一段 "x"。它不在字典里,不能当作一个单词整段用掉,这条路走不通,直接跳过,f[5] 还是 1。继续把起点往右挪,试下一段。
- 25答案 = 1整张表填满,最后一列 f[5] 就是答案。它等于 1,意思是把 codex 最优分割后只剩 1 个额外字符。回头看这条最优路线:code 从第 0 位接到第 4 位这一段是单词、零额外,末尾那个 x 谁也覆盖不了,是唯一的额外字符,正好 1 个。
⚠️ 容易写错的地方
✗ 错：贪心地每次都切最长的单词
✓ 对：用 f[i] 对所有命中的 j 取最小
最长匹配不一定最优,可能切短单词反而给后面留出更好分法,必须让动态规划枚举所有结尾在此的单词
✗ 错：f[i] 只写命中时的更新,忘了 f[i-1]+1
✓ 对：先写 f[i]=f[i-1]+1 保底再尝试压小
某些位置根本没有单词在此结尾,若不保底,f[i] 会取不到值或被漏算,额外字符必须允许存在
✗ 错：把子串比对写成从 i 往后取
✓ 对：取的是结尾在第 i 位的子串 s[j..i-1]
f[i] 管的是前 i 个字符,只有以第 i 位结尾的单词才能接到 f[i],起点 j 在左侧滑动
✗ 错：命中单词就立刻采纳、停止枚举
✓ 对：命中也要比一比 f[j] 是否更小
同一个 i 可能有多个单词结尾,不同起点的 f[j] 不同,要在其中取最小才是最优
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
unordered_set<string> ss(dictionary.begin(), dictionary.end());
int n = s.size();
int f[n + 1];
f[0] = 0;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] + 1;
for (int j = 0; j < i; ++j) {
if (ss.count(s.substr(j, i - j))) {
f[i] = min(f[i], f[j]);
}
}
}
return f[n];
}
};Java
import java.util.*;
class Solution {
public int minExtraChar(String s, String[] dictionary) {
Set<String> ss = new HashSet<>();
for (String w : dictionary) {
ss.add(w);
}
int n = s.length();
int[] f = new int[n + 1];
f[0] = 0;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] + 1;
for (int j = 0; j < i; ++j) {
if (ss.contains(s.substring(j, i))) {
f[i] = Math.min(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 平方增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字符串中的额外字符 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的状态和转移怎么定义?+
设 f[i] 为 s 前 i 个字符最优分割后最少剩的额外字符数。转移有两条:让第 i 个字符当额外字符,f[i]=f[i-1]+1;或枚举以第 i 位结尾的子串 s[j..i-1],若它是字典单词,则 f[i] 可取 f[j]。两者取最小,答案是 f[n]。
朴素做法慢在哪,怎么优化?+
朴素做法对每个 i 都往回枚举所有起点 j 并现截子串查哈希,是 O(n 的平方乘 L)。优化的常见办法是把字典里的单词反着插入字典树,固定右端 i、让左端沿这棵反向字典树往回走,一次走完就能找出所有以 i 结尾的单词,省掉反复截子串,总体降到 O(n 的平方)。
为什么用动态规划而不是贪心?+
贪心地每次切最长或最先匹配到的单词都可能错。某处切一个短单词,反而给后面留出更好的分割。只有让 f[i] 在所有以此结尾的单词里取 f[j] 最小,并和 f[i-1]+1 比较,才能保证全局最优,这正是动态规划的价值。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 字符串中的额外字符 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。