# 动态规划解决单词拆分问题详解
## 题目描述
给定一个字符串 `s` 和一个字符串列表 `wordDict`，判断是否可以用字典中的单词（可重复使用）拼接出 `s`。
**示例**
输入：`s = "leetcode", wordDict = ["leet", "code"]`
输出：`true`
解释：字符串可以分割为 `"leet"` 和 `"code"`。
---
## 解题思路
### 核心思想：动态规划
1. **定义状态**
定义一个布尔数组 `dp`，其中 `dp[i]` 表示字符串 `s` 的前 `i` 个字符是否可以被字典中的单词拼接而成。
2. **初始化**
`dp[0] = true`，因为空字符串默认可以被表示。
3. **状态转移**
对于每一个位置 `i`（从 `1` 到 `s.length()`），遍历所有可能的分割点 `j`（从 `0` 到 `i-1`）：
- 如果 `dp[j]` 为 `true`，说明前 `j` 个字符可以被分割。
- 检查子串 `s.substring(j, i)` 是否在字典中。
- 若满足条件，则 `dp[i] = true`，并跳出内层循环。
4. **最终结果**
返回 `dp[s.length()]`，即整个字符串是否可以被分割。
---
## 代码实现与注释
```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine(); // 读取字符串 s
int n = sc.nextInt(); // 读取字典长度
sc.nextLine(); // 处理换行符
String[] wordDict = new String[n];
for (int i = 0; i < n; i++) {
wordDict[i] = sc.nextLine().trim(); // 读取字典中的单词
}
System.out.println(wordBreak(s, wordDict)); // 调用核心方法
}
public static Boolean wordBreak(String s, String[] wordDict) {
boolean[] dp = new boolean[s.length() + 1]; // dp数组，长度比s多1，第一个索引 用于存放空字符
Set<String> wordSet = new HashSet<>(Arrays.asList(wordDict)); // 字典转为集合，方便快速查找
dp[0] = true; // 空字符串默认可分割
for (int i = 1; i <= s.length(); i++) { // 遍历所有可能的结束位置i
for (int j = 0; j < i; j++) { // 遍历所有分割点j
// 如果前j个字符可分割，且子串s[j..i)在字典中
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true; // 标记为可分割
break; // 无需继续检查其他j
}
}
}
return dp[s.length()]; // 返回最终结果
}
}
```
---
## 关键点解析
1. **字典转换为集合**
使用 `HashSet` 存储字典单词，将查找操作的时间复杂度从 `O(n)` 降为 `O(1)`。
2. **动态规划的双重循环**
- 外层循环遍历所有可能的结束位置 `i`，范围是 `[1, s.length()]`。
- 内层循环遍历所有分割点 `j`，范围是 `[0, i)`。
- 通过 `s.substring(j, i)` 提取子串，并在字典中查找。
3. **优化思路**
- 可记录字典中最长单词的长度 `maxLength`，在内层循环中，`j` 的范围只需从 `Math.max(0, i - maxLength)` 开始。
- 避免检查长度超过 `maxLength` 的子串，减少不必要的计算。
---
## 测试用例
### 示例1
输入：
```
leetcode
2
leet
code
```
输出：`true`
说明：字符串被分割为 `"leet"` 和 `"code"`。
### 示例2
输入：
```
applepenapple
2
apple
pen
```
输出：`true`
说明：分割为 `"apple" + "pen" + "apple"`。
### 示例3
输入：
```
catsandog
5
cats
dog
sand
and
cat
```
输出：`false`
说明：所有可能的分割都无法覆盖完整字符串。
---
## 总结
通过动态规划方法，我们高效地解决了单词拆分问题。核心思想是利用子问题的解来推导全局解，避免了暴力搜索的指数级复杂度。实际应用中，可通过进一步优化（如限制子串长度）提升性能。
---
## 为什么初始思路不可行？
### 初始思路的问题分析
用户最初的思路大致如下：
1. **输入处理**：将字符串 `s` 按空格分割为 `input1`，将字典视为 `input2`。
2. **匹配逻辑**：遍历 `input1` 的每个单词，检查是否存在于 `input2` 中。
3. **终止条件**：若某个单词不在字典中，直接返回 `false`；否则返回 `true`。
**看似合理，但存在以下严重问题：**
---
### 问题1：输入字符串并未预先分割
题目中的字符串 `s` **是连续且未被分割的**。
例如：
- 示例1中的 `s = "leetcode"` 是一个连续字符串，需要被动态分割为 `"leet"` 和 `"code"`。
- 但初始思路假设 `s` 已经被正确分割（如 `input1 = ["leet", "code"]`），这是完全错误的。
**关键矛盾**：如何分割 `s` 本身是题目需要解决的问题，而不是输入的直接条件。
---
### 问题2：无法处理动态分割
题目要求通过**动态分割**找到一种组合方式，使得所有子串都在字典中。
例如：
- `s = "applepenapple"` 需要分割为 `"apple" + "pen" + "apple"`。
- 初始思路直接将 `s` 按空格分割，但原字符串没有空格，导致无法正确解析。
**错误根源**：
- 用户代码中使用了 `split("\\s+")`，这会将 `s` 按空格分割，但题目中 `s` 是连续字符串，无法通过空格分割。
---
### 问题3：未考虑字典单词的重复使用
题目明确说明**字典中的单词可以重复使用**。
例如：
- 示例2中 `s = "applepenapple"`，字典中有 `"apple"`，需要重复使用两次。
- 初始思路仅检查 `input1` 中的单词是否在字典中，但 `input1` 是固定的分割结果，无法体现重复使用。
**错误逻辑**：
- 若输入字符串需要重复使用字典中的单词（如 `"apple"` 出现两次），初始方法无法动态生成这种组合。
---
### 问题4：时间复杂度高且不全面
假设 `s` 被分割为 `n` 个单词，字典有 `m` 个单词，初始思路的时间复杂度为 `O(n*m)`。
但动态规划方法通过预计算所有可能的分割点，时间复杂度为 `O(n^2)`，更高效且全面。
**关键对比**：
- 初始方法仅检查固定分割后的单词，可能遗漏其他合法分割方式。
- 动态规划通过双重循环覆盖所有可能的分割点，确保不漏解。
---
### 具体反例验证
以示例3为例：
输入：`s = "catsandog"`, `wordDict = ["cats", "dog", "sand", "and", "cat"]`
正确输出应为 `false`。
**初始思路的错误流程**：
1. 假设 `s` 被分割为 `["cats", "and", "og"]`（但 `"og"` 不在字典中）。
2. 直接返回 `false`。
**问题暴露**：
- 初始方法可能错误地认为分割是固定的，但实际上还有其他潜在分割方式（如 `"cat" + "sand" + "og"`），这些都需要被检查。
- 动态规划方法会遍历所有可能的分割点，发现所有分割方式均不合法，最终返回 `false`。
---
## 总结
初始思路的**核心问题**在于：
1. **错误假设输入已被分割**，忽视了题目中字符串的连续性。
2. **无法动态生成分割方案**，导致遗漏合法组合。
3. **未处理字典单词的重复使用**，逻辑不完整。
动态规划通过维护 `dp` 数组，逐字符检查所有可能的分割点，从根本上解决了这些问题，确保了正确性和高效性。