139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

My Answer 1: Wrong Answer (39 / 43 test cases passed.)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if len(wordDict) == 0:
            return False
        
        for i in range(0, len(wordDict)):
            string = s
            if wordDict[i] in string:
                string = string.replace(wordDict[i], '')
                for j in range(i+1, len(wordDict)):
                    if wordDict[j] in string:
                        string = string.replace(wordDict[j], '')
            if string == '':
                return True
        
        return False

첨엔 이해를 잘못해서 s 에 포함된 단어들만 wordDict 에 있어야 하는 줄 알았다가 아닌걸 알고

s 에 word 가 있으면 s 에서 그 word 를 지워주는 식으로 했는데

"cbca" | ["bc","ca"] -> False 이런 케이스를 고려하지 못함..ㅎ
(bc 를 지우면 ca 가 남아서 True 가 됨)

그래서 지우는 대신 다른 문자로 대체하는 방식도 해봤지만
"ddadddbdddadd" | ["dd","ad","da","b"] -> True 이럴 때 안됨
(dd 를 '.' 으로 대체하면 ddadddbdddadd -> .a.db.da. 가 돼서 False 가 됨)

Dynamic Programming

Solution 1: Runtime: 68 ms - 7.31% / Memory Usage: 14.6 MB - 20.16%

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for i in range(len(s) + 1)] #(1)
        dp[0] = True
        
        for i in range(len(s) + 1): #(2)
            for j in range(i):
                print(s[j:i])
                if dp[j] and s[j:i] in wordDict: #(3)
                    dp[i] = True
                    break #(4)
        
        return dp[len(s)] #(5)
        
    #(1) dp[i] = s[0:i] is breakable
    #(2) Considering all possible substrings of s.
    #(3) If s[0:j] is breakable and s[j:i] is breakable, then s[0:i] is breakable. Equivalently, if dp[j] is True and s[j:i] is in the wordDict, then dp[i] is True.
    #(4) Our goal is to determine if dp[i] is breakable, and once we do, we don't need to consider anything else. This is because we want to construct dp.
    #(5) dp[len(s)] tells us if s[0:len(s)] (or equivalently, s) is breakable.

7.31% 긴 해도.. 이해하긴 좋다

dp 값이 True 면 한 단어의 시작점을 의미

l e e t c o d e
T F F F T F F F T

dp[len(s)-1] 까지 모두 사전에 있으므로 dp[len(s)] = True

True: 새 단어 찾을 준비 됐다 | False: 사전에서 아직 못 찾았다

Solution 2: Runtime: 32 ms - 93.32% / Memory Usage: 14.4 MB - 63.43%

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True] + [False] * len(s)
        
        for indx in range(1, len(s) + 1):
            
            for word in wordDict:
                if dp[indx - len(word)] and s[:indx].endswith(word):
                    dp[indx] = True
            
        return dp[-1]

이건 빠르지만 이해는 안되는 DP...