Description:
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Solution:
Time Complexity : O(wordDict.length^s.length)
Space Complexity: O(s.length)
var wordBreak = function(s, wordDict, memo={}) {
// Return already solved for sentance
if(memo[s]!==undefined) return memo[s]
// Base case of yet unsolved sentance
if(s.length===0) return ['']
const output = []
for(const word of wordDict) {
if(s.indexOf(word)===0) {
const suffix = s.slice(word.length)
// All different sentances to make the suffix
const suffixWays = wordBreak(suffix, wordDict, memo)
// Add the word to all the different sentance combinations
const targetWays = suffixWays.map(way => word + (way.length ? ' ' : '') + way)
output.push(...targetWays)
}
}
memo[s] = output
return output
}
Top comments (0)