题解 | #训练聪明的牛#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 对于字符串 s 和词汇表 wordDict，我们定义状态 dp[i] 表示前 i 个字符能否拆分成一个或多个 wordDict 中的单词。
2. 第一个情况表示在 s 的前 i 个字符中有一个单词与 wordDict 中的某个单词相等。
3. 第二个情况表示存在一个位置 j，使得前 j 个字符已经被拆分成了若干个单词，且从第 j+1 到第 i 个字符组成的子串与 wordDict 中的某个单词相等。（例如，当 i=5 时，假设 dp[2] = True 且 s[2:5] = "cat" 在 wordDict 中，那么 s[:5] = "catsand" 就可以被拆分成 "cat" 和 "sand" 两个单词）
4. 最终返回 dp[len(s)] 即可。如果 dp[len(s)] 为 True，则表示 s 可以被拆分成 wordDict 中的单词，否则不能

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param wordDict string字符串一维数组 
# @return bool布尔型
#
class Solution:
    def wordBreak(self , s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        
        return dp[n]