139. 单词拆分
[此处请插入：动态规划（DP）状态转移过程示意图]
✨核心逻辑
本题采用 动态规划（DP） 的策略：
- 状态定义：定义布尔数组
dp，dp[i]表示字符串s的前i个字符（即s[0..i-1]）能否由wordDict中的单词拼接而成。 - 状态转移：对于每一个位置
i，尝试寻找一个分割点j（j < i）。如果dp[j]为true（即前j个字符可以成功拆分），并且s.substring(j, i)这个子串存在于字典wordDict中，说明前i个字符可以由前j个字符加上当前子串拼凑而成，因此dp[i] = true。 - 小优化：由于题目提示了字典中的单词最大长度为 20，所以内层循环切分时，
j只需要从max(0, i - 20)开始倒推即可，无需每次都从 0 遍历到i-1，大大提升了效率。 - 初始化：
dp[0] = true（空字符串可以拼成），这是动态规划的起点。
🔥代码实现（含详细变量注释）
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// wordSet：将字典转换为 HashSet，以便在 O(1) 时间内快速查找子串是否存在
Set<String> wordSet = new HashSet<>(wordDict);
// length：记录待检查字符串的总长度
int length = s.length();
// dp：动态规划数组，dp[i] 表示字符串 s 的前 i 个字符能否被成功拼接
// 数组大小为 length + 1，是因为需要表示空字符串（索引 0）到完整字符串（索引 length）的所有状态
boolean[] dp = new boolean[length + 1];
// 初始化：空字符串可以拼成，作为后续状态转移的基础
dp[0] = true;
// i：外层循环遍历整个字符串，作为当前需要判断的子串的终点（不包含 i）
for (int i = 1; i < dp.length; i++) {
// j：内层循环遍历分割点（起点）。
// 优化：由于字典中的单词最大长度为 20，从 i-20 开始即可，避免从 0 遍历导致的无用计算
for (int j = Math.max(0, i - 20); j < i; j++) {
// 核心状态转移：
// 1. dp[j] 必须为 true（说明前 j 个字符能拆）
// 2. 剩余的字符串 s.substring(j, i) 必须在字典中存在
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break; // 找到一个可行解即可，直接跳出内层循环
}
}
}
// 返回整个字符串能否被拼接的结果
return dp[length];
}
}
⏱️复杂度分析
时间复杂度：O(N^2)（最坏情况）。其中 N 是字符串 s 的长度。由于字典单词最大长度为 20，内层循环最多执行 20 次，切分和哈希查找是常数时间，因此实际时间复杂度为 O(N * 20) = O(N)，非常高效。
空间复杂度：O(N + M)，其中 N 是字符串长度，用于 dp 数组；M 是字典中所有字符的总长度，用于存储 wordSet。
注意：
Math.max(0, i - 20) :
由于字典中的单词最大长度为20，因此在判断 dp[i] 时，最后一个单词的长度最多为20，只需要枚举 i 前20个位置作为切割点。如果超过20，由于字典中不存在这么长的单词，匹配一定失败。同时前面的字符串是否可以拆分已经通过 dp[j] 保存，因此不会因为缩小搜索范围而遗漏结果。