[LeetCode] DP, BFS - 139. Word Break

문제

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

 

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

코드

DP

const wordBreak = (s, wordDict) => {
    if(!wordDict || wordDict.length === 0) return false;
    const set = new Set(wordDict);
    const dp = new Array(s.length + 1).fill(false);
    dp[0] = true;

    for(let end = 1; end <= s.length; end++) {
        for(let start = 0; start < end; start++) {
            // wordDict의 원소들을 순서대로 s와 비교해야함
            // end를 기준으로 계속 start를 늘리면서 wordDict에 글자가 있는지 비교
            // end는 새로운 start
            const w = s.slice(start, end);
            if(dp[start] && set.has(w)) {
                dp[end] = true
                break;
            }
        }
    }

    return dp[s.length];
}

BFS

const wordBreak = (s, wordDict) => {
    if(wordDict === null || wordDict.length === 0) return false;
    const set = new Set(wordDict);

    const visited = new Set();
    const q = [0];

    while(q.length) {
        const start = q.shift();
        if(!visited.has(start)) {
            for(let end = start + 1; end <= s.length; end++) {
                if(set.has(s.slice(start, end))) {
                    if(end === s.length) return true;
                    q.push(end);
                }
            }
            visited.add(start)
        }
    }

    return false
}