【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
程序员文章站
2022-05-08 14:33:59
...
题目:
给定一个非空字符串 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"]
输出:
[]
抛砖引玉
思路:
开始本题之前可以先理下单词拆分的逻辑
参考单词拆分的逻辑,s这个增加字符求解,递归传入索引index,返回s中index->s.length-1的解的集合。
递归逻辑:
从传入的索引开始向后枚举,存在满足条件(自己组成的单词在wordDict中)则,将其放入本轮结果数组中,另外本轮结果数组其他部分有后续自己提供及(helper(x))
- 参数:索引index
- 结束:遇到已经计算过的子集结果或者枚举到最后
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
let map = new Map(),
mapDict = new Map(),
len = s.length,
list = [],
_result = [];
for(let i = 0; i < wordDict.length;i++){
mapDict.set(wordDict[i])
}
list = helper(0);
for (let item of list) {
_result.push(item.join(' '));
}
function helper (index) {
// 记录子集较少重复递归
if (map.has(index)) return map.get(index)
let item = index === len? [[]]:[];
// 枚举指定索引index后能组成在wordDict中单词的组合
for (let i = index + 1; i <= len; i++) {
const word = s.substring(index, i);
if (mapDict.has(word)) {
let next = helper(i);
for (let i of next) {
item.push([word, ...i]);
}
}
}
map.set(index, item);
return item;
}
return _result;
};
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言
推荐阅读
-
一天一大 lee(解数独)难度:困难-Day20200915
-
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
-
一天一大 lee(冗余连接 II)难度:困难-Day20200917
-
【一天一大 lee】最大间距 (难度:困难) - Day20201126
-
一天一大 lee(N 皇后)难度:困难-Day20200903
-
【一天一大 lee】N皇后 II (难度:困难) - Day20201017
-
【一天一大 lee】插入区间 (难度:困难) - Day20201104
-
一天一大 lee(24点游戏)难度:困难-Day20200822
-
一天一大 lee(回文对)难度:困难-Day20200806
-
一天一大 lee(最短回文串)难度:困难-Day20200829