单词拆分II

#单词拆分II
#给一字串s和单词的字典dict,在字串中增加空格来构建一个句子，并且所有单词都来自字典。
#返回所有有可能的句子。
#EXAMPLE：
#给一字串lintcode,字典为["de", "ding", "co", "code", "lint"]
#结果为["lint code", "lint co de"]。

class Solution:
    """
    @param: s: A string
    @param: wordDict: A set of words.
    @return: All possible sentences.
    """
    def wordBreak(self, s, wordDict):
        # write your code here
        return self.helper(s, wordDict, {})

    def helper(self, s, wordDict, memory):
        if s in memory: #string如果有记录，直接调用返回以节省时间
            return memory[s]
        res = []
        for i in range(len(s)-1):
            cut = s[:i+1]
            if cut in wordDict:
                sub = self.helper(s[i+1:], wordDict, memory)
                for j in sub:
                    res.append(cut + ' ' + j)
        if s in wordDict:
            res.append(s)
        memory[s] = res #记住这个string有多少种拆分方法
        return res