Python DP solution in 11 lines

  • 3
    def wordBreak(self, s, wordDict):
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        M = {}
        def dfs(remain_str):
            if not remain_str: return ['']
            if remain_str in M: return M[remain_str]
            ret = []    
            for i in xrange(1,len(remain_str)+1):
                if remain_str[:i] in wordDict: 
                    for r in dfs(remain_str[i:]): 
                        ret.append( (remain_str[:i]+' '+r).strip() )
            M[remain_str] = tuple(ret)
            return ret
        return dfs(s)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.