欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【一天一大 lee】单词拆分 II (难度:困难) - Day20201101

程序员文章站 2022-05-08 14:33:59
...

【一天一大 lee】单词拆分 II (难度:困难) - Day20201101

题目:

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

  • 分隔时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例:

  1. 示例1:
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
  1. 示例2:
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
  1. 示例3:
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

抛砖引玉

思路:

开始本题之前可以先理下单词拆分的逻辑

参考单词拆分的逻辑,s这个增加字符求解,递归传入索引index,返回s中index->s.length-1的解的集合。

递归逻辑:
从传入的索引开始向后枚举,存在满足条件(自己组成的单词在wordDict中)则,将其放入本轮结果数组中,另外本轮结果数组其他部分有后续自己提供及(helper(x))

  • 参数:索引index
  • 结束:遇到已经计算过的子集结果或者枚举到最后

【一天一大 lee】单词拆分 II (难度:困难) - Day20201101

/**
 * @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 栏目
欢迎关注留言

公众号:前端小书童