[LeetCode][Python3] 140. Word Break II

Problem :

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

My Solution :

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:

def dfs(s):

if s in memo:

return memo[s]

res = []

for word in wordDict:

if s.startswith(word):

cases = dfs(s[len(word):])

for case in cases:

res.append([word] + case)

memo[s] = res

return res

memo = {'': [[]]}

dfs(s)

return [' '.join(case) for case in memo[s]]

Comment :

Memoization이 핵심이다.