目标
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 wordDict[i] 仅由小写英文字母组成
- wordDict 中的所有字符串 互不相同
思路
已知一个字符串列表 wordDict 和一个字符串 s，问能否用列表中的元素拼成该字符串，列表中的元素可以重复使用。
很明显需要使用动态规划来求解，假设当前列表元素 word 的长度为 l，子字符串 sub 的长度为 i，如果 sub.substring(0, i-l) 能由字典中的词拼成并且 word.equals(sub.substring(i-l, l)) 那么 sub 也能由字典中的词拼成。
代码
/**
* @date 2024-06-23 19:58
*/
public class WordBreak139 {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {
int length = word.length();
if (length <= i && dp[i - length] && word.equals(s.substring(i - length, i))) {
dp[i] = true;
}
}
}
return dp[n];
}
public boolean wordBreak_v1(String s, List<String> wordDict) {
int n = s.length();
char[] mem = new char[n + 1];
Arrays.fill(mem, '2');
return dfs(s, 0, wordDict, mem) == '1';
}
public char dfs(String s, int i, List<String> wordDict, char[] mem) {
int n = s.length();
if (i == n) {
return '1';
}
if (mem[i] != '2') {
return mem[i];
}
for (String word : wordDict) {
if (s.startsWith(word, i) && '1' == dfs(s, i + word.length(), wordDict, mem)) {
return mem[i] = '1';
}
}
return mem[i] = '0';
}
}
性能
最快的解法是使用记忆化搜索，可以剪枝缩小搜索范围。
