看到一个有点辣眼睛的吐槽：“拒绝背锅就被辞退，还是违法辞退！”这事换谁听了不窝火呢？
算法题：单词拆分
今天刷算法题的时候，遇到一个挺经典的题目：单词拆分。
题目是这样的：给一个字符串 s 和一个单词字典 wordDict，判断 s 是否可以通过字典中的单词拼接出来。注意，字典里的单词可以重复使用，但必须全部匹配。
问题分析
听着是不是有点像小时候拼拼图？不过别高兴太早，这题看起来简单，实际一不小心就被整糊涂。我们需要一个高效的算法解决，而不是用蛮力把所有可能的组合试一遍，毕竟输入太大的话，暴力法直接让你感受什么叫“超时惨案”。
最合适的思路是动态规划（Dynamic Programming，简称 DP）。动态规划的本质就是“把大问题拆解成小问题，然后解决小问题”。我总说，DP 和分手很像，别总想着一步到位，分阶段慢慢推进，最后目标自然就实现了。😂
解题思路
假设 dp[i] 表示字符串 s 的前 i 个字符是否能被字典拆分，那么转移方程是这样的：
dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
意思就是，如果能找到一个位置 j，使得 s[0...j] 可以拆分，且 s[j...i] 也在字典中，那么 s[0...i] 就可以拆分。
好，现在上代码，直接看实现👇：
Java 实现
import java.util.*;
public class WordBreak {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true; // 空字符串是可以拆分的
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
public static void main(String[] args) {
WordBreak wb = new WordBreak();
String s = "leetcode";
List<String> wordDict = Arrays.asList("leet", "code");
System.out.println(wb.wordBreak(s, wordDict)); // 输出: true
}
}
核心点解读
** dp[0] = true**：空字符串天然可以被拆分，这就好比考试还没开始，你至少能拿个基础分。两个循环：外层遍历 i，表示当前我们要验证字符串的长度；内层遍历j，拆分点在j，看s[j...i]是否在字典中。剪枝：只要找到一个合法的 j，就直接停止内层循环，节省计算。
优化思路
内层循环可以通过滑动窗口优化，但核心思路依然是一样的。如果再让你加点难度，比如返回所有可能的拆分方式，这题就可以变成回溯法结合记忆化的应用了。😎
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
