字符串中的额外字符 图解题解

「额外字符」到底数的是哪些字符

给字符串 s 和字典 dictionary，把 s 切成若干互不重叠的子串，每段都得是字典单词；塞不进单词的字符就是额外字符，求最少剩几个。题面两例：leetscode 切出 leet、code，中间的 s 落单，额外 1 个；sayhelloworld 切出 hello、world，开头 say 落单，答案 3。

2^8 种切法试不完，贪心抓长词又错在哪

leetscode 有 8 个字符间隙，每个切或不切，光切法就 2^8=256 种，枚举不动。贪心每次抓能配的最长词也靠不住：长词可能压着两个短词的接缝，占完反塞不进更多。字符归哪个词牵动整串，只能切小问题、从前缀问起。

f[i] 为什么定成前 i 个字符的最少额外

定义 f[i]：s 前 i 个字符最少剩几个额外字符——一维动态规划（把「前 i 个字符怎么切最省」存进数组，更长前缀直接取）。f[0] 是空串、零额外，f[0]=0 是 base case（不用再往下拆的最简起点），答案 f[n]。它是单词拆分（LeetCode 139）的计费版：拆不完的字符改成记一分。

第 i 个字符只有两种命运，取最小为什么一个不落

盯住第 i 个字符（从 1 数起），它只有两种命运。要么谁也不归、自己当额外，前 i 个最优＝前 i-1 个最优加一分，f[i]=f[i-1]+1，这一行兜住；要么它是某词典词的末字符，词覆盖 s[j:i]（第 j 个字符后到第 i 个收尾），这段零额外，f[i] 接 f[j]。

实现先把字典塞进哈希集合（O(1) 查某段是不是单词），对每个 i 枚举起点 j 从 0 到 i-1，截 s[j:i] 查，命中且 f[j] 更小就更新——这就是转移（由已算好的小格子推出当前格）。取最小填到 f[n] 即全局最少。命中不等于采纳：几个词同在 i 收尾，挑 f[j] 最小的接。

leetscode 的 f 表，哪两格是靠单词压下来的

九个字符，f 开十格，f[0]=0。前三格没词命中，保底：f[1]=1、f[2]=2、f[3]=3。f[4] 保底给 f[3]+1=4；j 从 0 起 s[0:4] 正是 leet，接 f[0]=0，f[4] 压到 0。

第 5-8 字符是 s、c、o、d，没词收尾，接着保底：f[5]=1、f[6]=2、f[7]=3、f[8]=4。f[9] 保底 f[8]+1=5；j 从 5 起 s[5:9] 正是 code，接 f[5]=1，f[9] 压到 1。题面输出 1：中间的 s 唯一额外。

漏写保底那一行，f[9] 为什么缩成 0

参考代码把 f 初始化成全 0，每轮第一件事是 f[i]=f[i-1]+1；这行一漏，没词命中的格子全停在 0，f[9] 缩成 0。方向也别错：内层截的必须是以第 i 位收尾的 s[j:i]，从 i 往后截整张表就接不上。

复杂度：外层 i、内层 j 约 n² 对，每对截子串比对，截取加哈希 O(L)（L 是子串最长长度），总时间 O(n²·L)，最坏 O(n³)；空间 O(n+M)。整串恰是一个词典词，命中一次 f[n] 清成 0。一个词都配不上，每格默认加一，f[n]=n。

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];
    }
}