문제푸는데 화가났으므로 칙칙한 배경ㅠ

139. Word Break

DP 풀이

우선 s길이가 1이거나

Time, Space complexity

S: s.length
W: wordDict.length

slice와 indexOf하는데에 s길이만큼 시간이 소요되므로 O(SW) * O(S) 만큼 소요된다.

time O(S^2 * W), space O(S)

var wordBreak = function(s, wordDict) {
    if(s.length===1 && wordDict.indexOf(s) === -1) return false;
    
    const dp = Array(s.length+1).fill(0);
    
    for(let i=0; i<s.length; i++){
        if(i>0 && !dp[i]) continue;
        
        for(let word of wordDict){
            if(s.slice(i).indexOf(word)===0) dp[i+word.length]=1;
        }
    }
    
    return dp[dp.length-1];
};