139. 单词拆分
题目描述
输入字符串 s 和字符串列表 wordDict（字典）。
判断能否把 s 完整地切成一段或多段，使每一段都是字典里的单词。字典里的单词可以反复使用，也不必全部用到。
能切则返回 true，否则返回 false。
示例 1
输入：s = "leetcode", wordDict = ["leet","code"] 输出：true
解释：切成 leet 和 code。
示例 2
输入：s = "applepenapple", wordDict = ["apple","pen"] 输出：true
解释：切成 apple、pen、apple，apple 用了两次。
示例 3
输入：s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] 输出：false
解释：任何切法都会剩下不在字典里的片段。
数据范围
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]只含小写英文字母。wordDict中没有重复单词。
解题思路
dp[i] 表示前 i 个字符能否拆分，若存在 j 使 dp[j] 且 s[j:i] 在字典中则成立。
为什么正确
dp[i] 确认前 i 个字符完整可拆分，不依赖未处理的后缀。
复杂度分析
Python 子串切片和哈希计入后，最坏时间 O(n³)；辅助空间 O(n+D)，D 为字典集合大小。
易错点
不能只按字符切分；每次转移要同时保证前缀可达和当前子串在字典中。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[-1]class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = 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] && words.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= (int)s.size(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && words.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp.back();
}
};func wordBreak(s string, wordDict []string) bool {
words := map[string]bool{}
for _, w := range wordDict {
words[w] = true
}
dp := make([]bool, len(s)+1)
dp[0] = true
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
if dp[j] && words[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[len(s)]
}var wordBreak = function(s, wordDict) {
const words = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && words.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
};function wordBreak(s: string, wordDict: string[]): boolean {
const words = new Set(wordDict);
const dp: boolean[] = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && words.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
};其他解法
自底向上的动态规划枚举切分点；记忆化搜索自顶向下枚举单词，只计算可达的状态。k 为单词数，L 为最长单词长度。
解法 2：记忆化搜索 时间 O(n·k·L)，空间 O(n)
can(i) 表示从下标 i 开始的后缀能否拆分。枚举字典里的每个单词，若它是 s 在下标 i 处的前缀，就递归判断 can(i + len(w))。每个下标的结果只算一次并缓存。
按单词枚举，字典小、单词短时很快，并且只访问能到达的下标。递归深度最多为 n。
from functools import lru_cache
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
@lru_cache(None)
def can(i):
if i == n:
return True
for w in wordDict:
if s.startswith(w, i) and can(i + len(w)):
return True
return False
return can(0)class Solution {
private Boolean[] memo;
public boolean wordBreak(String s, List<String> wordDict) {
memo = new Boolean[s.length()];
return can(s, wordDict, 0);
}
private boolean can(String s, List<String> words, int i) {
if (i == s.length()) return true;
if (memo[i] != null) return memo[i];
for (String w : words) {
if (s.startsWith(w, i) && can(s, words, i + w.length())) {
return memo[i] = true;
}
}
return memo[i] = false;
}
}class Solution {
vector<int> memo;
bool can(const string& s, const vector<string>& words, int i) {
if (i == (int)s.size()) return true;
if (memo[i] != -1) return memo[i];
for (const string& w : words) {
if (i + w.size() <= s.size() && s.compare(i, w.size(), w) == 0 && can(s, words, i + w.size())) {
return memo[i] = 1;
}
}
return memo[i] = 0;
}
public:
bool wordBreak(string s, vector<string>& wordDict) {
memo.assign(s.size(), -1);
return can(s, wordDict, 0);
}
};func wordBreak(s string, wordDict []string) bool {
n := len(s)
memo := make([]int, n)
var can func(i int) bool
can = func(i int) bool {
if i == n {
return true
}
if memo[i] != 0 {
return memo[i] == 1
}
for _, w := range wordDict {
if i+len(w) <= n && s[i:i+len(w)] == w && can(i+len(w)) {
memo[i] = 1
return true
}
}
memo[i] = 2
return false
}
return can(0)
}var wordBreak = function(s, wordDict) {
const n = s.length;
const memo = new Array(n).fill(undefined);
const can = (i) => {
if (i === n) return true;
if (memo[i] !== undefined) return memo[i];
for (const w of wordDict) {
if (s.startsWith(w, i) && can(i + w.length)) return (memo[i] = true);
}
return (memo[i] = false);
};
return can(0);
};function wordBreak(s: string, wordDict: string[]): boolean {
const n = s.length;
const memo: (boolean | undefined)[] = new Array(n).fill(undefined);
const can = (i: number): boolean => {
if (i === n) return true;
if (memo[i] !== undefined) return memo[i]!;
for (const w of wordDict) {
if (s.startsWith(w, i) && can(i + w.length)) return (memo[i] = true);
}
return (memo[i] = false);
};
return can(0);
}