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

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

/**
 * @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;
};