0139. Word Break
================
题目信息
--------
:题号: 0139. 单词拆分
:难度: Medium
:主题: 字符串、动态规划、记忆化搜索、位置可达性
:原题: `LeetCode 0139 `_
:重点: 用切分位置表示已完整覆盖的前缀,将指数切分树压缩为有限位置状态,并只从可达位置传播
题目重述
--------
给定非空字符串 ``s`` 和字典 ``wordDict``,判断能否把 ``s`` 按原顺序完整切分成一个或多个非空字典词。
每次使用不会消耗字典词,所以同一个词可以在不同位置重复使用。只需返回是否存在至少一种合法切分,不必
输出具体方案。
自建示例
--------
* ``s = "mintmint"``、``wordDict = ["mint"]``:可切为 ``mint | mint``,返回 ``true``;
* ``s = "applepenx"``、字典为 ``["apple", "pen"]``:前八个字符可覆盖,但末尾 ``x`` 无法覆盖,
返回 ``false``;
* ``s = "cars"``、字典为 ``["car", "ca", "rs"]``:``ca | rs`` 可行,不能因先尝试 ``car`` 失败
就否定其他切点。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool matchesAt(
const std::string& s,
int start,
const std::string& word
) {
const int wordLength = static_cast(word.size());
return start + wordLength <= static_cast(s.size()) &&
s.compare(start, wordLength, word) == 0;
}
bool searchEveryCut(
const std::string& s,
int start,
const std::vector& words
) {
if (start == static_cast(s.size())) {
return true;
}
for (const std::string& word : words) {
if (matchesAt(s, start, word) &&
searchEveryCut(
s,
start + static_cast(word.size()),
words
)) {
return true;
}
}
return false;
}
bool searchWithMemo(
const std::string& s,
int start,
const std::vector& words,
std::vector& memo
) {
if (start == static_cast(s.size())) {
return true;
}
if (memo[start] != -1) {
return memo[start] == 1;
}
for (const std::string& word : words) {
const int next = start + static_cast(word.size());
if (matchesAt(s, start, word) &&
searchWithMemo(s, next, words, memo)) {
memo[start] = 1;
return true;
}
}
memo[start] = 0;
return false;
}
bool propagateReachablePrefixes(
const std::string& s,
const std::vector& words
) {
const int length = static_cast(s.size());
std::vector reachable(length + 1, false);
reachable[0] = true;
for (int start = 0; start < length; ++start) {
if (!reachable[start]) {
continue;
}
for (const std::string& word : words) {
if (matchesAt(s, start, word)) {
const int end =
start + static_cast(word.size());
reachable[end] = true;
}
}
}
return reachable[length];
}
public:
bool wordBreak(
std::string s,
std::vector& wordDict
) {
return propagateReachablePrefixes(s, wordDict);
}
};
题解
----
原始选择空间:下一段取哪个字典词
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
从位置 ``start`` 开始,可以尝试所有与当前后缀前缀匹配的字典词;选择一个后,进入它末尾之后的新位置。
``searchEveryCut`` 正是这棵选择树。抵达字符串末尾说明每一段都来自字典,返回真;一个分支失败后还要尝试
其他词,因为不同长度的匹配词会产生不同切点。
这比枚举所有 ``n-1`` 个切缝再验证更早删除了非字典片段,但仍可能指数增长。例如许多短词都能匹配
``"aaaa..."`` 的前缀,不同切分前缀会反复到达相同 ``start``,再完整尝试相同后缀。
后缀只由位置决定
~~~~~~~~~~~~~~~~
到达 ``start`` 后,未来能否完成只取决于 ``s[start..]`` 和固定字典,不取决于此前用了哪些词。字典词不是
消耗品,所以状态中也不需要“剩余词集合”。``searchWithMemo`` 为每个位置保存三种状态:``-1`` 尚未计算、
``0`` 不可完成、``1`` 可以完成。每个后缀只展开一次,指数路径树被压缩为至多 ``n`` 个位置状态。
短路分支也有明确含义:找到一个匹配词且其后缀可完成,就足以把当前状态记为真;只有所有匹配词都失败,
才能记为假。
字符边界构成一张有向无环图
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
字符串有 ``0..n`` 共 ``n+1`` 个边界位置。若字典词 ``word`` 在 ``start`` 处匹配,就存在一条
``start -> start + word.length`` 的边。边总是向更大下标前进,因此图无环;题目等价于判断节点 ``n`` 是否
从节点 ``0`` 可达。
记忆化搜索从终点反问后缀能否完成;主解则按下标拓扑顺序正向传播。令 ``reachable[i]`` 表示前 ``i`` 个
字符能否被若干字典词完整覆盖。空前缀 ``reachable[0] = true`` 是传播起点,并不表示字典含空词;题目
字符串非空,最终仍需沿至少一条非空单词边才能到达 ``n``。
为什么只能从可达起点传播
~~~~~~~~~~~~~~~~~~~~~~~~
某个词即使在位置 ``start`` 与后缀匹配,若 ``s[0..start-1]`` 无法完整切分,这条局部匹配也不能属于从
零出发的完整方案。代码先检查 ``reachable[start]``,只从已有合法前缀延伸;匹配成功后把词尾边界标为
可达。不可达位置无需尝试全部字典词,既是正确剪枝,也删除无效字符串比较。
具体走读词的重复使用
~~~~~~~~~~~~~~~~~~~~
对 ``s = "mintmint"``、字典 ``["mint"]``:
.. list-table::
:header-rows: 1
* - 起始边界
- 当前状态
- 匹配与传播
* - ``0``
- ``reachable[0] = true``
- ``mint`` 匹配,标记 ``reachable[4]``
* - ``1..3``
- 不可达
- 全部跳过
* - ``4``
- ``reachable[4] = true``
- 再次尝试同一个 ``mint``,标记 ``reachable[8]``
* - ``8``
- 终点可达
- 返回 ``true``
字典词只定义边的匹配规则,每个可达位置都会重新遍历字典,所以重复使用自然发生,不需要复制词或维护
使用次数。
代码顺序与边界
~~~~~~~~~~~~~~
``matchesAt`` 先检查单词不会越过字符串末尾,再调用定长 ``compare``,避免构造临时子串。正向 DP 按
``start`` 递增处理;所有入边都来自更小下标,所以访问一个位置时,它的可达性已经不会再被更晚位置改变。
即使终点提前标真,继续扫描也不影响结果;也可据此增加提前返回,但不是正确性所必需。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用前缀可达 DP,避免递归深度,状态含义也直接对应“完整覆盖”。设字符串长度为 ``n``、字典词数
为 ``D``、最大词长为 ``L``,最多从 ``n`` 个可达位置尝试 ``D`` 个词,每次比较 ``O(L)``,最坏时间
``O(nDL)``、空间 ``O(n)``。记忆化搜索具有相同数量的位置状态和类似匹配上界,但使用递归栈;无记忆 DFS
最坏为指数时间。三种代码保留的是从路径枚举、状态合并到迭代可达性的真实演进。