Word Break II

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        function<vector<string>(int)> dfs = [&](int start) -> vector<string> {
            if (memo.count(start)) return memo[start];
            if (start == (int)s.size()) return {""};
            vector<string> out;
            for (int end = start + 1; end <= (int)s.size(); ++end) {
                string word = s.substr(start, end - start);
                if (!dict.count(word)) continue;
                for (auto& tail : dfs(end)) {
                    out.push_back(word + (tail.empty() ? "" : " " + tail));
                }
            }
            return memo[start] = out;
        };
        return dfs(0);
    }
};

func wordBreak(s string, wordDict []string) []string {
    dict := map[string]bool{}
    for _, w := range wordDict {
        dict[w] = true
    }
    memo := map[int][]string{}
    var dfs func(start int) []string
    dfs = func(start int) []string {
        if v, ok := memo[start]; ok {
            return v
        }
        if start == len(s) {
            return []string{""}
        }
        out := []string{}
        for end := start + 1; end <= len(s); end++ {
            word := s[start:end]
            if !dict[word] {
                continue
            }
            for _, tail := range dfs(end) {
                if tail == "" {
                    out = append(out, word)
                } else {
                    out = append(out, word+" "+tail)
                }
            }
        }
        memo[start] = out
        return out
    }
    return dfs(0)
}

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        dict_set = set(wordDict)
        memo: dict[int, List[str]] = {}

        def dfs(start: int) -> List[str]:
            if start in memo:
                return memo[start]
            if start == len(s):
                return [""]
            out: List[str] = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word not in dict_set:
                    continue
                for tail in dfs(end):
                    out.append(word if tail == "" else word + " " + tail)
            memo[start] = out
            return out

        return dfs(0)

function wordBreak(s, wordDict) {
    const dict = new Set(wordDict);
    const memo = new Map();
    const dfs = (start) => {
        if (memo.has(start)) return memo.get(start);
        if (start === s.length) return [""];
        const out = [];
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.slice(start, end);
            if (!dict.has(word)) continue;
            for (const tail of dfs(end)) {
                out.push(tail === "" ? word : word + " " + tail);
            }
        }
        memo.set(start, out);
        return out;
    };
    return dfs(0);
}

class Solution {
    private String s;
    private Set<String> dict;
    private Map<Integer, List<String>> memo = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.dict = new HashSet<>(wordDict);
        return dfs(0);
    }

    private List<String> dfs(int start) {
        if (memo.containsKey(start)) return memo.get(start);
        List<String> out = new ArrayList<>();
        if (start == s.length()) {
            out.add("");
            memo.put(start, out);
            return out;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (!dict.contains(word)) continue;
            for (String tail : dfs(end)) {
                out.add(tail.isEmpty() ? word : word + " " + tail);
            }
        }
        memo.put(start, out);
        return out;
    }
}

function wordBreak(s: string, wordDict: string[]): string[] {
    const dict = new Set<string>(wordDict);
    const memo = new Map<number, string[]>();
    const dfs = (start: number): string[] => {
        if (memo.has(start)) return memo.get(start)!;
        if (start === s.length) return [""];
        const out: string[] = [];
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.slice(start, end);
            if (!dict.has(word)) continue;
            for (const tail of dfs(end)) {
                out.push(tail === "" ? word : word + " " + tail);
            }
        }
        memo.set(start, out);
        return out;
    };
    return dfs(0);
}