140. Word Break II

嗯，超时了

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = []
        self.dfs(s, 0, "", res, wordDict)
        return res
    def dfs(self, s, start, temp, res, wordDict):
        if start == len(s):
            res.append(temp)
            return 
        for i in range(start, len(s)):
            t = s[start:i+1]
            if t in wordDict:
                end = i+1
                if end != len(s):
                    self.dfs(s, end, temp+t+' ', res, wordDict )
                else:
                    self.dfs(s, end, temp+t, res, wordDict)

剪枝了的做法

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = []
        f = []
        self.dfs(s, 0, [], res, wordDict,f)
        return res
    def dfs(self, s, start, temp, res, wordDict,f):
        if start == len(s):
            res.append(' '.join(temp[:]))
            return True
        if start in f:
            return False
        found = False
        for i in range(start+1, len(s)+1):
            if i in f:
                continue
            t = s[start:i]
            if t in wordDict:
                print t
                temp.append(t)
                if self.dfs(s, i, temp, res, wordDict, f):
                    found = True
                temp.pop()
        if not found:
            f.append(start)
        return found