/**
 * Brute Force - DFS
 * Hash Set - Distinct Keys
 * Time O(2^N) | Space O(N)
 * https://leetcode.com/problems/word-break/
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = (s, wordDict) => {
    const wordSet = new Set(wordDict); /* Time O(N)   | Space O(N) */

    return canBreak(s, wordSet); /* Time O(2^N) | Space O(N) */
};

var canBreak = (s, wordSet, start = 0) => {
    const isBaseCase = start === s.length;
    if (isBaseCase) return true;

    return dfs(s, wordSet, start); /* Time O(2^N) | Space O(N) */
};

var dfs = (s, wordSet, start) => {
    for (let end = start + 1; end <= s.length; end++) {
        /* Time O(N) */
        const word = s.slice(start, end); /* Time O(N)   | Space O(N) */

        const _canBreak =
            wordSet.has(word) &&
            canBreak(s, wordSet, end); /* Time O(2^N) | Space O(N) */
        if (_canBreak) return true;
    }

    return false;
};

/**
 * DP - Top Down
 * Array - Memoization
 * Hash Set - Distinct Keys
 * Time O(N^3) | Space O(N)
 * https://leetcode.com/problems/word-break/
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = (s, wordDict) => {
    const wordSet = new Set(wordDict); /* Time O(N)         | Space O(N) */
    const memo = new Array(s.length).fill(
        null,
    ); /*                   | Space O(N) */
    const start = 0;

    return canBreak(
        s,
        wordSet,
        start,
        memo,
    ); /* Time O(N * N * N) | Space O(N) */
};

var canBreak = (s, wordSet, start, memo) => {
    const isBaseCase1 = s.length === start;
    if (isBaseCase1) return true;

    const hasSeen = memo[start] !== null;
    if (hasSeen) return memo[start];

    return dfs(s, wordSet, start, memo); /* Time O(N * N * N) | Space O(N) */
};

var dfs = (s, wordSet, start, memo) => {
    for (let end = start + 1; end <= s.length; end++) {
        /* Time O(N) */
        const word = s.slice(start, end); /* Time O(N) | Space O(N) */

        const _canBreak =
            wordSet.has(word) &&
            canBreak(s, wordSet, end, memo); /* Time O(N * N) */
        if (_canBreak) {
            memo[start] = true;
            return true;
        }
    }

    memo[start] = false;
    return false;
};

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Hash Set - Distinct Keys
 * Time O(N^3) | Space O(N)
 * https://leetcode.com/problems/word-break/
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = (s, wordDict) => {
    const wordSet = new Set(wordDict); /* Time O(N)         | Space O(N) */
    const tabu = initTabu(s); /*                   | Space O(N) */

    canBreak(s, wordSet, tabu); /* Time O(N * N * N) | Space O(N) */

    return tabu[s.length];
};

const initTabu = (s) => {
    const tabu = new Array(s.length + 1).fill(false); /* Space O(N) */

    tabu[0] = true;

    return tabu;
};

var canBreak = (s, wordSet, tabu) => {
    for (let end = 1; end <= s.length; end++) {
        /* Time O(N) */
        checkWord(s, wordSet, end, tabu); /* Time O(N * N) | Space O(N) */
    }
};

var checkWord = (s, wordSet, end, tabu) => {
    for (let start = 0; start < end; start++) {
        /* Time O(N) */
        const word = s.slice(start, end); /* Time O(N) | Space O(N) */

        const canBreak = tabu[start] && wordSet.has(word);
        if (!canBreak) continue;

        tabu[end] = true;

        return;
    }
};

/**
 * Tree Traversal - BFS
 * Queue - Level Order Space O(WIDTH)
 * Hash Set - Distinct Keys
 * Array - Seen
 * Time O(N^3) | Space O(N)
 * https://leetcode.com/problems/word-break/
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    const wordSet = new Set(wordDict); /* Time O(N)         | Space O(N) */
    const queue = new Queue([0]); /*                   | Space O(N) */
    const seen = new Array(s.length).fill(
        false,
    ); /*                   | Space O(N) */

    return bfs(
        queue,
        s,
        wordSet,
        seen,
    ); /* Time O(N * N * N) | Space O(N + WIDTH) */
};

const bfs = (queue, s, wordSet, seen) => {
    while (!queue.isEmpty()) {
        for (let level = queue.size() - 1; 0 <= level; level--) {
            /* Time O(N) */
            if (canWordBreak(queue, s, wordSet, seen))
                return true; /* Time O(N * N) | Space O(N + WIDTH) */
        }
    }

    return false;
};

var canWordBreak = (queue, s, wordSet, seen) => {
    const start = queue.dequeue();

    const hasSeen = seen[start];
    if (hasSeen) return false;

    if (canBreak(queue, s, start, wordSet))
        return true; /* Time O(N * N) | Space O(N + WIDTH) */

    seen[start] = true; /*               | Space O(N) */
    return false;
};

var canBreak = (queue, s, start, wordSet) => {
    for (let end = start + 1; end <= s.length; end++) {
        /* Time O(N) */
        const word = s.slice(start, end); /* Time O(N) | Space O(N) */

        if (!wordSet.has(word)) continue;

        queue.enqueue(end); /*           | Space O(WIDTH) */

        const _canBreak = end === s.length;
        if (_canBreak) return true;
    }

    return false;
};