x 139. Word Break

Word Break - LeetCodeLeetCode

ideation

Check how many ways to climb stairs

dp + substring

time: O(m x n^2), n is the length of string, m is the length of wordDict

space: O(n)

var wordBreak = function(s, wordDict) {
    const arr = new Array(s.length + 1).fill(false);
    arr[0] = true;

    for (let i = 1; i < arr.length; i++) {

        for (const word of wordDict) {
            const possible = arr[i - word.length];
            if (possible === true) {
                const sub = s.substring(i - word.length, i);
                if (sub === word) {
                    arr[i] = true;
                    break;
                }
            }

        }
    }


    return arr[s.length];
};

Brute Force: TLE

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
let status = {
    done: false,
};
var wordBreak  = function(s, wordDict) {
    status = {
        done: false,
        flag: false,
    };

    validate(s, wordDict);
    return status.flag;
};

function validate(s, wordDict) {
    if (status.flag === true) {
        return;
    }

    if (s.trim().length === 0) {
        status.flag = true;
        return;
    }

    for (let i = 0; i < wordDict.length; i++) {
        const currWord = wordDict[i];
        const regex = new RegExp(currWord, '');
        if (s.includes(currWord)) {
            const newStr = s.replace(regex, ' ')
            validate(newStr, wordDict);
        }
    }
}