博文中会简要介绍Leetcode P0140题目分析及解题思路。
“Word Break II”这道题是p0139的变形题，也是比较典型的一维费用背包问题，不过这道题动态规划结束后，还需要一次深度优先搜索。
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.
一维费用背包问题属于比较经典的动态规划问题。同样，在这里s的长度可以看作背包的容量，wordDict中每个单词的长度可以看作物品的费用。这道题的递推表达式和p0139基本一致，如下，
令dp[i]表示s[0:i-1]能否由wordDict中的词拼接而成，
dp[0] = true,
显然长度为0时可以由0个单词拼接而成，
dp[i] = dp[i] || (dp[i-L] && word == s.substring(i-L, i), L = word.length() for every word in wordDict,
对于wordDict中的每个单词，当i的长度大于该单词，我们关注s[i-L:i-1]的子串是否和当前相等，且前缀是否能够被拼接。以上任意一个条件不满足，则为false。
然后可以做一次剪枝，这样不容易超时，如果当前字符串s不能被拼接，那么也就不用进行下一步的深度优先探索了。
如果发现当前字符串s可以被拼接，则进入后续的DFS，遍历当前的动态规划数组，得到每一个s[0:i]可行的拼接方法，最终就可以得到整个字符串的。
以下是Java的题解代码实现。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
int N = s.length();
boolean[] dp = new boolean[N+1];
dp[0] = true;
for (int i1=1; i1<=N; ++i1) {
for (String word: wordDict) {
int L = word.length();
if (i1-L < 0)
continue;
String segment = s.substring(i1-L, i1);
dp[i1] = dp[i1] || (dp[i1-L] && word.equals(segment));
}
}
// Pruning
if (!dp[N])
return new ArrayList<>();
List<String>[] partitions = new List[N+1];
for (int i1=1; i1<=N; ++i1) {
if (!dp[i1])
continue;
partitions[i1] = new ArrayList<>();
for (String word: wordDict) {
int L = word.length();
if (i1-L >= 0
&& word.equals(s.substring(i1-L, i1))
&& dp[i1-L]) {
if (i1-L == 0)
partitions[i1].add(word);
else {
for (String prev: partitions[i1-L])
partitions[i1].add(prev+" "+word);
}
}
}
}
return partitions[N];
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
int N = s.length();
bool *dp = new bool[N+1];
dp[0] = true;
for (int i1=1; i1<=N; ++i1) {
dp[i1] = false;
for (string word: wordDict) {
int L = word.length();
if (i1 < L)
continue;
string segment = s.substr(i1-L, L);
dp[i1] = dp[i1] || (dp[i1-L] && segment == word);
}
}
if (!dp[N])
return vector<string>();
vector<vector<string>> partitions(N+1, vector<string>());
for (int i1=1; i1<=N; ++i1) {
if (!dp[i1])
continue;
for (string word: wordDict) {
int L = word.length();
if (i1-L >= 0
&& word == s.substr(i1-L, L)
&& dp[i1-L]) {
if (i1-L == 0)
partitions[i1].push_back(word);
else {
for (string prev: partitions[i1-L])
partitions[i1].push_back(prev+" "+word);
}
}
}
}
return partitions[N];
}
};