Word Break II

Problem statement

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.

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: []

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

My solution

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
    const dict = new Set(wordDict)
    const memo = new Map();
    
    function dfs(start) {
        if (start > s.length - 1) {
            return [[]]
        }
        
        if (memo.has(start)) {
            return memo.get(start)
        }
        
        let localResult = []
        
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.substring(start, end)
            
            if (dict.has(word)) {
                let nextWords = dfs(end)
                
                for (const next of nextWords) {
                    localResult.push([word, ...next])
                }
            }
        }
        
        memo.set(start, localResult)
        return localResult;
    }
    
    const result = dfs(0)
    
    return result.reduce((acc, curr) => {
        acc.push(curr.join(" "))
        return acc;
    }, [])
};