[LeetCode每日一题]140. Word Break II
2020/3/11大约 2 分钟
题目如下:
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.
Example 1:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
140. Word Break II 这道题在139. Word Break的基础上要求返回所有符合要求的句子。这道题同样可以用动态规划解决。设状态空间为dp[s.length+1],dp[i]表示前i个字符组成的句子,DP的过程需要两层循环,外层循环变量i从1到s.length,表示当前计算的是s的从0到i的子串;内层循环变量j表示子串最后一个单词的长度,从1到i和最大单词长度的较小值。检查单词subString(i-j,i)是否在字典中,dp[i-j]是否非空(非空表示s的从0到j-i的子串合法),若两条同时满足,则将所有合法字符串添加到dp[i]中。 然而上述算法在提交后会有一个s="aaaaaaaaaaa...b" dict={"a","aa","aaa",...} 的测试用例爆内存,解决方法是在执行上述算法前判断s,是否可以由字典中的单词构成。判断过程即139. Word Break的代码。 修改后,实现代码如下:
class Solution {
public List wordBreak(String s, List wordDict) {
if (!canBreak(s, wordDict)) {
return new ArrayList<>();
}
int len = s.length();
int maxLen = 0;
int minLen = Integer.MAX_VALUE;
Set dict = new HashSet<>();
for (String string : wordDict) {
dict.add(string);
maxLen = Math.max(maxLen, string.length());
minLen = Math.min(minLen, string.length());
}
List[] dp = new ArrayList[len + 1];
dp[0] = new ArrayList<>();
dp[0].add("");
for (int i = 1; i <= len; i++) {
dp[i] = new ArrayList<>();
for (int j = minLen; j <= i && j <= maxLen; j++) {
String sub = s.substring(i - j, i);
if (dict.contains(sub) && !dp[i - j].isEmpty()) {
for (String string : dp[i - j]) {
dp[i].add(string + (string == "" ? "" : " ") + sub);
}
}
}
}
return dp[len];
}
public boolean canBreak(String s, List wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
int maxLen = 0;
for (String word : wordDict) {
maxLen = Math.max(maxLen, word.length());
}
dp[0] = true;
Set dict = new HashSet<>();
dict.addAll(wordDict);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= i && j <= maxLen; j++) {
if (dp[i - j] && dict.contains(s.substring(i-j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}