力扣 139. 单词拆分 python AC

动态规划

class Solution:
    def wordBreak(self, s, wordDict) -> bool:
        size = len(s)
        dp = [False] * (size + 1)
        dp[0] = True
        for i in range(1, size + 1):
            for word in wordDict:
                size2 = len(word)
                if size2 <= i and dp[i - size2] and s[i - size2:i] == word:
                    dp[i] = True
                    break
        return dp[size]

定义dp[i]的状态为：s字符串到第i位为止可以被列表中元素代表

--遍历字符串每一位

  --遍历列表每个元素

    --如果元素长度不大于当前字符串位置，且 字符串位置减元素长度 状态为真（到这步之前的字符串能够被列表中元素表示），且这段字符串和元素相等

      --设为真，并跳出循环，到字符串下一个位置

--返回dp最后一位的状态