wordBreak.py

# https://leetcode.com/problems/word-break-ii/submissions/

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        n = len(s)
        trie = {}
        for word in wordDict:
            node = trie
            for letter in word:
                node = node.setdefault(letter, {})
            node['_'] = None

        memo = [None] * (n)
        for start in range(n-1, -1, -1):
            fail = False
            node = trie
            position = start
            memo[start] = []
            for position in range(start, n):
                if '_' in node and memo[position]:
                    word = s[start:position]
                    for alternative in memo[position]:
                        memo[start].append('{} {}'.format(word, alternative))

                if s[position] not in node:
                    fail = True
                    break
                else:
                    node = node[s[position]]

            if not fail and '_' in node:
                memo[start].append(s[start:])
        return memo[0]

s = 'appletapplet'
wordDict = ['apple','applet', 'pen', 'top', 'let', 'app']
solution = Solution()
print(solution.wordBreak(s, wordDict))