python实现leetcode之139. 单词拆分

解题思路

动态规划
如果前一个点结束的串是可以切分的，并且从那个点到目前的位置的子串在字典里，当前节点之前的串就是可以切分的

139. 单词拆分

代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        N = len(s)
        word_set = set(wordDict)
        dp = [True] + [False for c in s]  # dp[0] == True

        index = 1
        while index <= N:
            for left in range(index-1, -1, -1):
                if dp[left] and s[left:index] in word_set:
                    dp[index] = True
                    break
            index += 1
        return dp[N]