题目
来源：139.单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明
- 拆分时可以重复使用字典中的单词
- 你可以假设字典中没有重复的单词
示例1
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"
示例2
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple" 注意你可以重复使用字典中的单词
示例3
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
分析
方法1：回溯法
首先将字典列表转换为 Set，这样每次在字典中查找有无单词的时间复杂度为 O(1)。遍历字符串 s，逐个增加当前单词的字符数量，若字典中包含当前单词，递归判断剩下的字符串；否则返回 false。直到最后判断的单词为空字符串时，说明字符串 s 已遍历结束，返回 true。
这样做有个问题，在某次判断至字符串 s 的某个位置时，该位置之后的子字符串可能在之前的过程中已经被判断为 false，为了不重复计算，用一个变量 mem 记录字符串 s 每个字符位置之后的子字符串是否已经被判断为 false。
时间复杂度：O(n^2) 空间复杂度：O(n)
方法2：动态规划
dp[i] 表示 i 位之前的字符串是否满足条件，dp[0] = true 表示空字符串是满足条件的。遍历字符串，判断每个字符位置之前的字符串是否满足条件。
时间复杂度：O(n^2) 空间复杂度：O(n)
解答
方法1：回溯法
class Solution {
private boolean[] mem; // 记录字符串 s 每个字符位置之后的子字符串是否已经判断过
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict); // 把字典列表转换为 Set，每次在字典中查找的时间复杂度为O(1)
mem = new boolean[s.length()];
return backtrack(s, 0, set);
}
private boolean backtrack(String s, int start, Set<String> set) {
if (s.length() == 0) return true; // 字符串为空时，表示已经遍历完
if (mem[start]) return false; // 如果当前位置之后的字符串已经判断为 false，则无需再计算
for (int i = 0; i < s.length(); i++) { // 逐个增加字符
if (set.contains(s.substring(0, i + 1))) { // 如果当前字符串在字典中存在，则继续判断其之后的字符串
if (backtrack(s.substring(i + 1, s.length()), start + i + 1, set)) {
return true; // 当前字符串在字典中存在，并且其之后的字符串在字典中也存在，则返回 true
}
}
}
mem[start] = true; // 遍历结束，说明从当前位置之后的字符串不满足条件
return false;
}
}
方法2：动态规划
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
Set<String> set = new HashSet<>(wordDict);
dp[0] = true; // 空字符串满足条件
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true; // 第 i 位之前的字符串满足条件
break;
}
}
}
return dp[s.length()];
}
}