示例 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"]
输出:
[]

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

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))
}