[리트코드] 139. Word Break / Javascript

문제주소 :https://leetcode.com/problems/word-break/

Word Break - LeetCode

---

<문제 설명>

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 ▒ 

처음에는 완전탐색으로 풀었는데, 시간초과가 발생했던 문제이다. 하여 DP를 사용해 풀었다.

 

기본적인 개념은 다음과 같다. 예를 들어 s="leetcode", wordDict = ["leet", "code"]일 때, 반복문을 통해 s를 한글자 한글자씩 늘려가며 체크하도록 해야한다. 이렇게 해야하는 이유는, 이렇게 해야 s를 한번 탐색하는 동안 정답을 찾을 수 있기 때문이다.

 

반복문을 통해 s를 증가시키며 체크하므로, 인덱스를 i라고 하면, "leetcode"에 대해서 i는 0부터 7까지 증가할 것이다. 

이 방식으로, s.slice(0, i)를 하면, s에서 확인하고 싶은 부분들을 잘라낼 수 있다.

i = 0 -> s.slice(0,i) = ""
i = 1 -> s.slice(0,i) = "l"
i = 2 -> s.slice(0,i) = "le"
i = 3 -> s.slice(0,i) = "lee"
i = 4 -> s.slice(0,i) = "leet"
...

 

이렇게 잘라내면서, 각 글자가 wordDict에 포함되어 있는지 확인한다. 

이때 확인하는 방법에서 dp를 사용하게 되는데, 원리는 이렇다.

for(let i = 0; i < s.length+1; i++){
        for(let j = 0; j < wordDict.length; j++){
            const word = wordDict[j];
            const word_len = word.length;
            if(dp[i-word_len] && s.slice(i-word_len, i) === word){
                dp[i] = true;
            }
        }
    }

첫 반복문은 s에 대해 한글자씩 탐색 범위를 늘려가는 반복문이고, 두 번째 반복문은 wordDict의 각 word를 차례대로 접근하기 위한 반복문이다.

 

그 후 조건문이 dp값을 지정해주는 부분인데, 해당 위치의 dp값을 true로 만들어주는 조건은(해당 위치까지는 wordDict의 단어들로 구성되어 있음을 알려주는 조건은) 다음과 같다.

1) dp[i-word_len]: word가 속하기 전까지의 s는 true인 s인가?

2) s.slice(i-word_len, i) === word: s의 (i-word_len)부터 i까지가 word랑 같은가?

 

사실 2)번은 뻔한 말이다. s = "leetcode"에서 "code"가 속해있는지를 보려면, s[4]부터('c'부터) s[7]까지('e'까지)를 가져와서 "code"와 비교해보아야 한다. 그 얘기를 하고 있는 것이다.

s = "leetcode" / word = "code" -> leet"code" 와 "code" 비교

 

1)번이 핵심인데, 해당 단어가 나타나기 전까지는 옳은(true값을 내줄 수 있는) s였는가를 보는 것이다. 다시 한번 s ="leetcode", word = "code"일 경우를 보면, 엄연히 "leetcode"안에는 "code"가 들어있다. 이 때, "code"가 s에서 나타나기 이전까지(예시에서는 "leet")부분이 옳은 부분이어야 의미가 있다.

쉽게 말해서 만약 s = "lootcode"라고 했을 때, word("code")는 s안에 있지만 어차피 앞 부분이 wordDict에 포함된 단어가 아니므로 "code"를 확인할 필요도 없이 false임을 알 수 있다.

반면 s="leetcode"의 경우, 앞 단어인 "leet"가 wordDict에 이미 포함되있으므로, "code"까지 확인을 해준다면, 최종 결과로 true를 낼 수 있다. 이 경우에는 "code"를 확인하는 것이 의미가 있다는 뜻이다.

 

이를 쉽게 체크해주기 위해 dp를 사용한 것이다. "code"가 나타나기 직전 인덱스를 idx라고 했을 때, dp[idx]= true일 때만, code를 확인해주는 것이 의미가 있다. 

 

for(let i = 0; i < s.length+1; i++){
        for(let j = 0; j < wordDict.length; j++){
            const word = wordDict[j];
            const word_len = word.length;
            if(dp[i-word_len] && s.slice(i-word_len, i) === word){
                dp[i] = true;
            }
        }
    }

코드를 다시 가져와 설명을 해보자면, s의 인덱스 i에 대해, i-word_len가 true일 때만 s를 slice하여 word와 확인하도록 해놓았다.

s = "leetcode" , word = "code"이고, i=8일 때를 생각해보자. 

i=8, word_len=4 이므로, dp[8-4] = dp[4]를 우선 확인한다. dp[4]는 뭐냐? 이전에 s를 슬라이싱했던 "leet"와 wordDict의 단어들을 비교했던 결과이다.

wordDict에 "leet"가 있으니, dp[4]에는 "제가 담당한 부분은 "leet"인데요(s.slice(0,4)), wordDict에도 "leet"가 있네요!" 해서 true값이 저장되어 있을 것이다.

dp[4]가 true값이니, dp[8]의 입장에서 "이미 이전에 true였으니, 이제 내가 true값만 주면 결과값으로 true를 내보낼 수 있겠구나!" 가 되는 것이다.

 

결과적으로 요약해보자면, 이 문제의 핵심은, 어떤 word가 등장하기 전까지의 s가 true인지 확인하고, true일 경우에만, 새로운 word와 s의 나머지 부분을 비교하는 것이다.

직관적으로는 잘 이해가 되지 않을 수 있으나, 직접 그려보면서 풀다보면 더 이해가 잘 될 수 있을 것이라고 생각한다.

 

 

<코드(Javascript)>

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const dp = [true];
    for(let i = 0; i < s.length; i++){
        dp.push(false);
    }
    
    for(let i = 0; i < s.length+1; i++){
        for(let j = 0; j < wordDict.length; j++){
            const word = wordDict[j];
            const word_len = word.length;
            if(dp[i-word_len] && s.slice(i-word_len, i) === word){
                dp[i] = true;
            }
        }
    }
    
    return dp[dp.length-1];
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest