139. Word Break

这一题是判断正确错误，需要用一个列表来记录下从某个坐标起再也找不到，字典中的单词能够继续走下去了。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        f = []
        return self.dfs(0, s, wordDict, f)
      
    def dfs(self, start, s, wordDict, f):
        if start == len(s):
            return True
        if start in f:
            return False
        for i in range(start+1, len(s)+1):
            if i in f:
                continue
            sp = s[start:i]
            if sp in wordDict and self.dfs(i, s, wordDict, f) :
                return True 
        f.append(start)
        return False

动态规划的做法

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        d = [False for i in range(len(s)+1)]
        d[0] = True
        for i in range(len(s)):
            for j in range(i+1):
                if d[j] and (s[j:i+1] in wordDict):
                    d[i+1] = True
                    break
        return d[-1]