LeetCode - Word Break(139)

DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        check = ''
        
        for i in range(len(s) - 1):
            check += s[i]
            if wordDict.count(check) == 1 and wordDict.count(check + s[i + 1]) == 0:
                check = ''
        
        check += s[-1]
        
        if wordDict.count(check) == 1:
            check = ''

        if len(check) == 0:
            return True
        else:
            return False

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        L = len(s)
        dp = [False]*(L+1)
        dp[0]=True
        for i in range(1,L+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    print(s[j:i])
                    dp[i] = True
        return dp[-1]

참고)
https://zhenyu0519.github.io/2020/02/22/lc139/