[7월 4주차] 풀이 공유

[hyunahOh]

타임아웃 나던 풀이

const cache = new Set();

var wordBreak = function(s, wordDict) {
    if (wordDict.includes(s)) {
        return true;
    }

    const possibleWords = wordDict.filter((word) => {
        return s.startsWith(word);
    }) // ["cats", "cat"]

    while (possibleWords.length > 0) {
        const possibleWord = possibleWords.pop(); // "cats"
        const tail = s.slice(possibleWord.length); // tail = "andog"
        cache.add(possibleWord);
        if (cache.has(tail) || wordBreak(tail, wordDict)) {  // wordBreak("andog", ...)
            return true;
        }
    }

    return false;
};

수정한 풀이

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict, cache = {}) {
    if (wordDict.includes(s)) {
        return true;
    }

    if (s in cache) {
        return cache[s];
    }

    for (let word of wordDict) {
        if (s.startsWith(word)) {
            const tail = s.slice(word.length); // tail = "andog"
            if (wordBreak(tail, wordDict, cache)) {  // wordBreak("andog", ...)
                cache[tail] = true;
                return true;
            } else {
                cache[tail] = false;
            }
        }
    }

    return false;
};

[Choozii]

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const cache = {};
    const words = {};

    for(let i=0;i<wordDict.length;i++){
        words[wordDict[i]] = true;
    }

    const recursive = (word) => {

        if(cache[word] !== undefined){
            return cache[word];
        }

        if(words[word]){
            return true;
        }

        for(let i=1;i<word.length;i++){
            const left = word.slice(0,i);
            const right = word.slice(i);

            if(words[left]){
                 if(recursive(right)){
                    cache[word] = true;
                    return true;
                }else if(!recursive(right)){
                    cache[word] = false;
                }
            }
        }

        return false;
    }

    return recursive(s);

};

[intothedeep]

dp + substring

ideation

Check how many ways to climb stairs

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);
        }
    }
}

[Choozii]

https://leetcode.com/problems/word-break/