word break2

[mengyushi]

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=547722&highlight=Uber%2BATG

题目就是 LeetCode 140 Word Break II。比如说 输入 dictionary = { i, like, ice, cream, icecream, man, go, mango} input = “ilikemangoicecream” 要求输出 i like mango ice creami like mango icecreami like man go icecreami like man go ice cream

[mengyushi]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        N = len(s)
        memorize = {N:[""]}    
        words = set(wordDict)

        def dfs(i):
            if i in memorize: return memorize[i]
            memorize[i] = [s[i:j]+(rest and " "+rest) for j in range(i+1,N+1) if s[i:j] in words for rest in dfs(j)]
            return memorize[i]

        return dfs(0)