[알고리즘] 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.

초기 아이디어

그리디 알고리즘을 이용했었다.
해당 단어를 만들면 set에서 있으면 초기화한 뒤 다시 찾고 최종적으로 해당 단어가 비어있으면 잘 만들어진 것이라고 생각했다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        temp = ""
        wordDict = set(wordDict)
        for i in s:
            temp += i
            
            if temp in wordDict:
                temp = ""
                
        if temp == "":
            return True
        else:
            return False

반례

엣지 케이스를 반영하지 못했다.

"aaaaaaa", set = {"aaaa", 'aaa'} 케이스는 aaa가 2번 반복되면서 a가 결국엔 마지막에 남는다.

다이나믹 프로그래밍

해당 문제는 다이나믹 프로그래밍을 통해 반복되는 부분을 줄일 수 있다.

구체적으로 엣지 케이스에 대해 살펴보자.

위의 그림에서와 같이 처음부터 단어들을 살피면서 한단어로 가능한 부분까지 체크한다.
그리고 가능하다고 표시된 부분부터 해당 단어로 표현되는 부분들을 체크한다.

위의 방법을 반복한다.

말로 설명하면 이해가 안될 수 있다.

코드로 보면서 확인해보자.

구현

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        
        for i in range(len(s)+1):
            if dp[i]: # 해당 단어부터 가능하다면..?
                for j in range(i+1, len(s)+1):
                    if s[i:j] in wordDict: ## 해당 단어까지 어떻게든 만들어지는 경우
                        dp[j] = True
        
        return dp[-1]