A more readable version of Stephan's code with Python, 99% percentile


  • 0
    X

    So the idea is recursion (DFS) with memoization. Start with index i (i=0), we check to see if s[i:j] is a word, if it is, keep doing it for the rest of the string.
    To reduce extra work:
    i. we only check till either the end of the string or max word length, whichever is smaller
    ii. use memoization, where we keep track of the substrings that we have done along the way (lower branches) and reuse them instead of redoing the work. e.g. the "dog" in "catsanddog" can be reused by both 'cat sand' and 'cats and'

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: List[str]
            """
            wordDict = set(wordDict)
            maxWordL = len(max(wordDict,key=len)) if wordDict else 0
            # memoization stores the index i and the list of valid substrings from that point on
            memoization={len(s):['']}
            
            def dfs(i):
                if i not in memoization:
                    memoization[i] = []
                    for j in xrange(i+1,min(i+maxWordL+1, len(s)+1)):
                        if s[i:j] in wordDict: 
                             for sentence in dfs(j):
                                    if sentence: 
                                        memoization[i].append(s[i:j]+' '+sentence)
                                    else:
                                        memoization[i].append(s[i:j])
                return memoization[i]
            
            return dfs(0)
            
    

Log in to reply
 

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