Word Break

[kokocan12]

Problem

When a string and a word dictionary are given, find a string can be completed by composition of words in dictionary.
Same word can be used more than once.

Approach

Using brute force, we can inspect about the every substrings.
The code is below.

const wordBreak = function(s, wordDict) {
    const dict = new Map();
    const cache = new Map();
    wordDict.forEach(word => dict.set(word, true));
    
    
    function dfs(s) {
        if(s.length === 0) return true;
        if(cache.get(s) !== undefined) return cache.get(s);
        
        let res = false;
        
        for(let i=0; i<s.length; i++) {
            const substr = s.slice(0, i+1);
            
            if(dict.get(substr)) {
                const rest = s.slice(i+1, s.length);
                res = true;
                res = res && dfs(rest);
                if(res) break;
            }
        }
        cache.set(s, res);
        return res;
    }
    
    return dfs(s);
};

But this solution has a high time complexity.

Better solution

Using dp, we can solve this faster.
When s is "leetcode" and dictionary is ["leet", "code"],
dp[8] is true, because index 8 is the last index of the string.
dp[7] is false, because 'e' is not in the dictionary.
dp[6] is false, because 'de' is not in the dictionary.
dp[5] is false, because 'ode' is not in the dictionary.
dp[4] is true, because 'code' is in the dictionary.
dp[3] is false, because 't' is not in the dictionary.
dp[2] is false, because 'et' is not in the dictionary.
dp[1] is false, because 'eet' is not in the dictionary.
dp[0] is true, because 'leet' is in the dictionary.

The code is below.

const wordBreak = function(s, wordDict) {
    
    const dp = new Array(s.length + 1).fill(false);
    dp[s.length] = true;
    
    for(let i=dp.length-1; i>=0; i--) {
        if(dp[i] === true) {
            for(word of wordDict) {
                const substr = s.slice(i-word.length, i)
                if(word === substr) {
                    dp[i-word.length] = true;    
                }
            }    
        }
    }
    return dp[0];
};