[JS] Word Break

🔒 문제 (LeetCode 139)

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.

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.

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘

DP

dp[i+1] = i번째까지 포함한 문자열로 잘랐을 때 wordDict에 해당되는 단어가 문자열에 존재하는지 boolean 값 저장

모든 문자를 순서대로 시작점으로 두고 길이를 늘려가며 wordDict에 존재하는지 검사 

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const len = s.length
    let dp = new Array(len + 1).fill(false)
    dp[0] = true
    
    for(let i = 1; i <= len; i++) {
       for(let j = 0; j < i; j++) {
           const str = s.substring(j, i)
           if(dp[j] && wordDict.includes(str)) {
               dp[i] = true
               break
           }
       }
    }
    
    return dp[len]
};

BFS

주어진 문자열을 두 개로 쪼개는 과정을 반복하여 wordDict에 존재하는 문자열로만 이루어져있다면 true 반환.

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const len = s.length
    const visited = new Set()
    const q = [s]
    
    while(q.length) {
        const cur = q.shift()
        
        if(wordDict.includes(cur)) return true
        
        for(let i = 0; i < cur.length; i++) {
            const str = cur.substring(0, i)
            const next = cur.substring(i, cur.length)
            if(!visited.has(next) && wordDict.includes(str)) {
                q.push(next)
                visited.add(next)
            }
        }
    }
    
    return false
}