[leetcode] 139. Word Break

문제 설명

링크
문자열s와 단어들의 배열 wordDict 가 주어졌을 때, wordDict 내의 단어들로 문자열을 만들 수 있는지 여부를 구하는 문제

접근 - DP

• dp[i] = dp[j] && s[j+1:i+1] in wordDict

코드

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