Word Break Variants

// Can we segment? O(n²) with set, O(n × maxWordLen) with trie
function canSegment(s, wordSet) {
    const n = s.length;
    const dp = new Array(n + 1).fill(false); dp[0] = true;
    for (let i = 1; i <= n; i++)
        for (let j = 0; j < i; j++)
            if (dp[j] && wordSet.has(s.slice(j, i))) { dp[i] = true; break; }
    return dp[n];
}

// Count ways to segment
function countSegments(s, wordSet) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0); dp[0] = 1;
    for (let i = 1; i <= n; i++)
        for (let j = 0; j < i; j++)
            if (dp[j] && wordSet.has(s.slice(j, i))) dp[i] += dp[j];
    return dp[n];
}

// All valid segments (backtracking + memoization)
function allSegments(s, wordSet) {
    const memo = new Map();
    function dfs(start) {
        if (memo.has(start)) return memo.get(start);
        if (start === s.length) return [''];
        const result = [];
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.slice(start, end);
            if (wordSet.has(word)) {
                const rest = dfs(end);
                for (const r of rest) result.push(r ? word + ' ' + r : word);
            }
        }
        memo.set(start, result);
        return result;
    }
    return dfs(0);
}