Python, two solutions: using a prefix tree and using dynamic programming


  • 0
    G

    When expressing complexities, |s| is the length of s, |d| is the length of wordDict and m is the maximum length of the words in wordDict.

    Prefix tree - O(|d| m) setup + O(|s| |d|) runtime and O(|d| m) space.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            tree = {}
        
            for word in wordDict:
                branch = tree
                for c in word:
                    branch = branch.setdefault(c, {})
                branch[None] = None
        
            possibilities = {id(tree): tree}
        
            for c in s:
                newpossibilities = {}
        
                for p in possibilities.itervalues():
                    try:
                        branch = p[c]
                    except KeyError:
                        continue
                    if None in branch:
                        newpossibilities[id(tree)] = tree
                        if len(branch) == 1:
                            continue
                    newpossibilities[id(branch)] = branch
        
                possibilities = newpossibilities
        
            return id(tree) in possibilities
    

    Dynamic programming - O(|s| m) time and O(1) time.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            wordDict = set(wordDict)
            valid = [False] * (len(s) + 1)
            valid[0] = True
            
            for i in xrange(1, len(s) + 1):
                for j in xrange(i - 1, -1, -1):
                    if valid[j] and s[j:i] in wordDict:
                        valid[i] = True
                        break
            
            return valid[-1]

Log in to reply
 

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