class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
max_len = max(map(len, wordDict))
for i in range(len(s) + 1):
for j in range(i - 1, max(i - max_len - 1, -1), -1):
if s[j:i] in wordDict and dp[j]:
dp[i] = True
return dp[len(s)]