作为一个在代码堆里摸爬滚打的程序员，今天看到B站的校招薪资爆出来那一刻，我的眼睛都直了！33k+1k房补×15薪，这个“算法岗”直接给我整破防了！😱
算法题：单词拆分
聊一道经典的算法题：单词拆分。听着名字挺文艺，但做起来一点也不文艺，简直就是算法界的拼图游戏。
题目意思很简单：给你一个字符串 s 和一个“字典” wordDict，问你能不能把 s 完全拆成字典里的单词组合。比如说，s = "leetcode"，wordDict = ["leet", "code"]，结果是 true，因为 s 可以拆成 leet 和 code，它俩都在字典里。
别看题目简单，细想一下，你会发现这其实是一个经典的动态规划问题。动态规划，听着挺吓人，但实际上就是“打家劫舍”的高配版，拆分问题，优化路径。不过话说回来，第一次接触这题，我脑子里的弹幕是：“能不能简单点，我代码写得不太好。”
思路解析
简单说，这题可以用动态规划（DP）来解。核心是构造一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能否被拆分成字典中的单词。
基本步骤是这样的：
定义状态：
dp[i]为true，表示s[0:i]是可以通过字典中的单词组合而成的；否则为 false。
转移方程：
对于每个位置 i，只要找到一个位置j（0 ≤ j < i），使得dp[j]为true，且s[j:i]在wordDict中，那么dp[i]就为true。翻译成代码就是： if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
}
初始化：
dp[0] = true，因为空字符串是可以被“拆分”的。
结果：
最终答案是 dp[s.length()]。
实现代码
下面直接上代码，配点注释方便大家理解：
import java.util.*;
public class WordBreak {
public static boolean wordBreak(String s, List<String> wordDict) {
// 转换为哈希集合，快速查找
Set<String> wordSet = new HashSet<>(wordDict);
// 定义 DP 数组，初始值为 false
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) {
String s = "leetcode";
List<String> wordDict = Arrays.asList("leet", "code");
System.out.println(wordBreak(s, wordDict)); // 输出 true
}
}
核心细节与优化
时间复杂度：
外层循环跑了一遍 s，内层循环最多也跑了s，所以最坏时间复杂度是O(n²)；如果字典查找用 HashSet，时间复杂度大约是O(1)。
空间复杂度：
dp数组占了O(n)的空间；字典转 HashSet需要额外空间。
注意边界：
字符串可能为空、字典可能为空，这些都需要在代码中提前处理，比如直接返回 false。
解题不光靠算法，还靠“资源配置”。字典不够用，就像打游戏装备差，根本撑不到最后，跪得比谁都快。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
