139. Word Break

Optimized one: mainly index using

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s:
            return False
        n = len(s) 
        dp = [False] * (n + 1)
        dp[0] = True
        for j in range(1, n+1):
            for h in range(j):
                if dp[h] and s[h:j] in wordDict:
                    dp[j] = True
                    break
        print(dp)
        return dp[-1]

My first solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s:
            return False
        n = len(s) 
        dp = [False] * n
        for j in range(n):
            if s[0:j+1] in wordDict:
                dp[j] = True
                continue
            for h in range(j):
                if dp[h] and s[h+1:j+1] in wordDict:
                    dp[j] = True
        #print(dp)
        return dp[n-1]