leetcode-javascript
leetcode-javascript copied to clipboard
单词拆分 II-140
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明:
分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
示例 1:
输入:
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"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-break-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
动态规划和单词拆分 139 的思路是一样的。
只不过每次可以分割的时候,把当前可以分割成的所有字符串都保存在一个数组里放入 dp[i]
中,那么下次再回头找这个 dp[i]
的时候,就可以拿出前面所有拼出的组合,再和新的词拼接即可。
这题的坑在于,官方的这个用例会爆栈:
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
用一个技巧可以绕过去,在最开始的时候先把 s
的所有字符去重后保存在数组中,再把 wordDict
中的所有字符去重后保存在数组中,对比两个数组的长度。如果 s数组
的长度 > wordDict数组
的长度,那么说明 wordDict
一定无法分割成 s
字符,直接返回空数组即可。
let wordBreak = function (s, wordDict) {
let uniqSChars = uniq(s.split(""))
let uniqWordDictChars = uniq(wordDict.join(""))
if (uniqSChars.length > uniqWordDictChars.length) {
return []
}
let n = s.length
if (!n) {
return []
}
let wordSet = new Set(wordDict)
let dp = []
dp[0] = [""]
for (let i = 1; i <= n; i++) {
let res = []
for (let j = i; j >= 0; j--) {
let word = s.slice(j, i)
if (wordSet.has(word)) {
if (dp[j] && dp[j].length) {
for (let prev of dp[j]) {
res.push(prev ? prev + " " + word : word)
}
}
}
}
dp[i] = res
}
return dp[n]
}
function uniq(arr) {
return Array.from(new Set(arr))
}