# LeetCode-单词拆分

## 记忆化递归

Posted by Jae on November 1, 2020

### 1、单词拆分(139)

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

输入: s = "leetcode", wordDict = ["leet", "code"]



输入: s = "applepenapple", wordDict = ["apple", "pen"]

注意你可以重复使用字典中的单词。 示例 3：



#### 1.1、思路

public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
Set<String> set = new HashSet<>();

wordDict.forEach(word -> set.add(word));
return helper(s, n, set);
}

private boolean helper(String s, int end, Set<String> set){
if (end == 0){
return true;
}
int i = end - 1;
while (i >= 0){
// 递归判断
if (set.contains(s.substring(i, end)) && helper(s, i, set)){
return true;
}
i--;
}
return false;
}


设f[i] 表示前i个字符组成的子串是否满足题意



f[0] = true


public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
int[] f = new int[n+1];
f[0] = 1;

Set<String> set = new HashSet<>();
wordDict.forEach(word -> set.add(word));

return helper(s, n, f, set);
}

private boolean helper(String s, int end, int[] f, Set<String> set){
if (f[end] == 1){
return true;
}

if (f[end] == -1){
return false;
}

int i = end - 1;
while (i >= 0){
if (set.contains(s.substring(i, end)) && helper(s, i, f, set)){
f[end] = 1;
return true;
}
i--;
}
f[end] = -1;
return false;
}


### 2. 单词拆分II

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

[
"cats and dog",
"cat sand dog"
] 示例 2：

s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

[] #### 2.2 思路


public List<String> wordBreak(String s, List<String> wordDict) {
int n = s.length();

Set<String> set = new HashSet<>();
wordDict.forEach(word -> set.add(word));
List<String> ans = new ArrayList<>();
helper(s, n, set, new ArrayList<>(), set);
return ans;
}
private void helper(String s, int end, Set<String> set, List<String> list, List<String> ans){
if (end == 0){
// 将单词拼接成句子
StringBuilder sb = new StringBuilder();
for (int i = list.size()-1; i >= 0; i--){
sb.append(list.get(i));
if (i > 0){
sb.append(" ");
}
}
ans.add(sb.toString());
return;
}

int i = end - 1;
while (i >= 0){
if (set.contains(s.substring(i, end))){
list.add(s.substring(i, end));
helper(s, i, set, list, ans);
// 回溯
list.remove(list.size()-1);
}
i--;
}
return;
}


public List<String> wordBreak(String s, List<String> wordDict) {
int n = s.length();
int[] f = new int[n+1];
f[0] = 1;
List<List<String>>[] F = new List[n+1];
for (int i = 0; i < F.length; i++){
F[i] = new ArrayList<>();
}

Set<String> set = new HashSet<>();
wordDict.forEach(word -> set.add(word));
List<String> ans = new ArrayList<>();
helper(s, n, f, F, set);
// F[end]中存储的单词即是最终的结果
for (List<String> l : F[n]){
StringBuilder sb = new StringBuilder();
for (int i = l.size()-1; i >= 0; i--){
sb.append(l.get(i));
if (i > 0){
sb.append(" ");
}
}
ans.add(sb.toString());
}
System.out.println(F);
return ans;
}

private boolean helper(String s, int end, int[] f, List<List<String>>[] F, Set<String> set){
if (f[end] == 1){
return true;
}
if (f[end] == -1) {
return false;
}

int i = end - 1;
while (i >= 0){
if (set.contains(s.substring(i, end)) && helper(s, i, f, F, set)){
f[end] = 1;
if (F[i].size() == 0){
F[end].add(Arrays.asList(s.substring(i, end)));
}else{
for (List<String> l : F[i]) {
List<String> t = new ArrayList<>();
t.add(s.substring(i, end));
t.addAll(l);
F[end].add(t);
}
}
}
i--;
}
if (f[end] == 0){
f[end] = -1;
return false;
}
return true;
}


< script src = " / js / bootstrap.min.js " >