LeetCode 140. Word Break II (javascript solution)

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
}

Blog

LeetCode 140. Word Break II (javascript solution)

codingpineapple

Description:

Solution:

Join Our Newsletter. No Spam, Only the good stuff.

Related