[LeetCode] 140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

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

单词拆分II。题意跟139题很接近。139题问的是字符串S是否可以被wordDict中的单词们拼接起来（单词可以重复使用），本题请你返回的是拼接的具体结果是什么。

思路是DFS递归。回忆一下139题的做法，dp[j]的含义是S中以S[j]作为结尾的子串是否存在于wordDict。如果某一个dp[j]为true，同时你还需要去看一下s.substring(j, i)，其中j比i小，是否存在于wordDict，以确定整个S是否能满足题意。等于说是你看到S的左半边的DP值为true了，你去试着找找看右半边是否存在于wordDict以判断整个S是否能被拼接。这道题可以试着用先去找后缀/右半边的方式递归去判断S是否能被拼接起来。

时间O(n^3)

空间O(n^3)

Java实现

 1 class Solution {
 2     public List<String> wordBreak(String s, List<String> wordDict) {
 3         Set<String> set = new HashSet<>();
 4         for (int i = 0; i < wordDict.size(); i++) {
 5             set.add(wordDict.get(i));
 6         }
 7         return helper(s, set, new HashMap<String, List<String>>());
 8     }
 9 
10     private List<String> helper(String s, Set<String> set, HashMap<String, List<String>> map) {
11         // corner case
12         if (s.length() == 0) {
13             return new ArrayList<>();
14         }
15 
16         // normal case
17         if (map.containsKey(s)) {
18             return map.get(s);
19         }
20         List<String> res = new ArrayList<>();
21         for (int j = 0; j < s.length(); j++) {
22             if (set.contains(s.substring(j, s.length()))) {
23                 if (j == 0) {
24                     res.add(s.substring(j, s.length()));
25                 } else {
26                     List<String> temp = helper(s.substring(0, j), set, map);
27                     for (int k = 0; k < temp.size(); k++) {
28                         String t = temp.get(k);
29                         res.add(t + " " + s.substring(j, s.length()));
30                     }
31                 }
32             }
33         }
34         map.put(s, res);
35         return res;
36     }
37 }

LeetCode 题目总结

[LeetCode] 140. Word Break II

推荐阅读