wordbreak用dp而非暴力回溯，因暴力会重复判断同一子串（如"eetcode"），dp通过dp[i]表示前i字符是否可拆分并缓存结果，避免重复计算；状态必须定义为前缀整体可拆分才能写出转移方程。
为什么 wordBreak 用 DP 而不是暴力回溯？
因为暴力递归会重复判断同一子串是否可拆分，比如 "leetcode" 中多次检查 "eetcode"、"etcode" 是否能被字典覆盖。DP 的核心是缓存中间结果——用 dp[i] 表示 s.substr(0, i) 是否可拆分，从左到右填表，避免重复计算。
常见错误是把状态定义成「以 i 结尾的子串能否拆」，但这样无法和前面状态拼接；必须定义为「前 i 个字符整体能否拆」，才能写出转移方程：dp[j] = true 且 s.substr(j, i-j) 在字典中 → dp[i] = true。
- 字典用
unordered_set<string></string>，O(1) 查找；别用vector或list，否则每次find是 O(n) - 内层循环 j 从 0 到 i-1，但可以提前 break：如果
s.substr(j, i-j).length()> 最长单词长度，跳过 - 初始化
dp[0] = true（空字符串算合法），这是转移起点
wordBreak 的边界条件怎么处理？
输入为空、字典为空、有空字符串元素——这三类情况最容易崩。C++ 里 substr 对越界索引不抛异常而是截断，导致逻辑静默错误。例如 s = "a", i = 1, j = 1 时 s.substr(1, 0) 返回空串，若字典含 "" 就误判成功。
- 提前检查字典：过滤掉空字符串，
dict.erase("")或构造时跳过 - 对每个
i，j 循环只取到max(0, i - maxWordLen)，避免生成过长子串 -
s.empty()直接返回true（按题意，空串可被拆分为零个词）；但有些 OJ 要求返回false，得看具体题目约束
C++ 里 substr 和内存性能怎么权衡？
频繁调用 s.substr(j, i-j) 会触发字符串拷贝，最坏 O(n²) 时间 + 高内存开销。尤其当单词短、字符串长时（如字典全是单字母，s 长 1e4），可能 TLE 或 MLE。
立即学习“C++免费学习笔记（深入）”；
替代方案是用哈希滚动或字典树剪枝，但工程中更实用的是预计算所有可能子串哈希值，或改用指针比较：
- 用
string_view替代substr（C++17），避免拷贝：dict.count(string_view(s).substr(j, i-j)) - 若编译器不支持 C++17，手动传
const string& s, int l, int r，在查找函数里用s.compare(l, r-l, word) - 注意
string_view不拥有数据，确保s生命周期长于它
LeetCode 139 和 140 的 DP 状态设计差异在哪？
139 只要判断是否可行（布尔 DP），140 要返回所有方案（需存路径）。后者不能直接在 dp[i] 存 vectordp[j] == true 时才向下搜 s.substr(j, i-j)。
- 140 必须加记忆化 DFS，否则重复搜索相同后缀；用
unordered_map<int vector>></int>缓存位置 i 开始的所有拆法 - 不要在 DP 表里存完整句子，只存分割点或前驱索引，最后统一重构
- 输出顺序依赖字典遍历顺序，若要求字典序，先对
wordDict排序
真正卡住人的往往不是状态转移本身，而是子串切分时的索引偏移、空串处理、以及 substr 拷贝带来的隐式性能衰减——这些地方一错，本地测得通，线上就超时或越界。
