Leetcode 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings).
Please reload the code definition to get the latest changes.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        dp = [False] * n
        for word in wordDict:
            if s.startswith(word):
                dp[len(word)-1] = True
    
        for i in range(n):
            for j in range(i + 1):
                if dp[j]:
                    if s[j+1:i+1] in wordDict:
                        dp[i] = True
        if dp[n-1]:
            return True
        return False