140. Word Break II

Difficulty:
Related Topics:
Similar Questions:

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Solution

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
  var dp = Array(s.length);
  var map = {};
  var res = [];

  for (var i = 0; i < wordDict.length; i++) {
    map[wordDict[i]] = true;
  }

  return find(s, map, dp, 0);
};

var find = function (s, map, dp, index) {
  if (dp[index]) return dp[index];

  var str = '';
  var tmp = null;
  var len = s.length;

  dp[index] = [];

  for (var i = index; i < len; i++) {
    str = s.substring(index, i + 1);
    if (!map[str]) continue;
    if (i === len - 1) {
      dp[index].push(str);
      break;
    }
    tmp = find(s, map, dp, i + 1);
    for (var j = 0; j < tmp.length; j++) {
      dp[index].push(str + ' ' + tmp[j]);
    }
  }

  return dp[index];
};

Explain:

dp[i] 代表 s.substring(i)wordDict 里的词组成的方式。

Complexity: