139.Word Break

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan 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".

Method 1 DP O(n^2) time, O(n) space

• Construct a dp array of size n+1 indicating whether s[:i] can be constructed from the dictionary

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in xrange(len(dp)):
            for j in xrange(0, i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]