leetcode 单词拆分 II python

把子字符串对应的分解方法都保存下来
时间复杂度还是高，贴出来记录一下

class Solution(object):
    def wordBreak(self, s, wordDict, thisBreak=[], tail_shortcuts={}, isRoot=True):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        if isRoot:
            tail_shortcuts.clear()
        if len(s)==0:
            tail_shortcuts[s]=[]
            return []
        this_shortcuts=[]
        break_cur=1
        while (break_cur<=len(s)):
            if s[:break_cur] in wordDict:
                if isRoot:
                    thisBreak[:]=[]
                if s[break_cur:] not in tail_shortcuts:
                    self.wordBreak(s[break_cur:],wordDict,thisBreak+[s[:break_cur]],tail_shortcuts,False)
                if s[break_cur:]=='':
                    this_shortcuts.append([s[:break_cur]])
                else:
                    for shortcut in tail_shortcuts[s[break_cur:]]:
                        this_shortcuts.append([s[:break_cur]]+shortcut)
            break_cur+=1
        tail_shortcuts[s]=this_shortcuts
        if isRoot:
            return map(lambda x: " ".join(x), this_shortcuts)
        else:
            return None