[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]