140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

139. Word Break 를 응용해보려고 했는데... 이게 모든 조합을 찾는 건 아니라서 실패함

Solution 1: Runtime: 44 ms - 56.66% / Memory Usage: 14.5 MB - 85.97%

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        cache={}
        
        def wordbr(s):
            if s not in cache: 
                result=[]
                for w in wordDict:
                    if s[:len(w)]==w:
                        if len(s)==len(w):
                            result.append(w)
                        else:
                            for word in wordbr(s[len(w):]):
                                result.append(w+" "+word)
                cache[s]=result
            return cache[s]
        
        return wordbr(s)

['dog'] => ['sand dog'] & ['and dog'] => ['cat sand dog', 'cats and dog']
맨 뒤에 단어를 기준으로 word 들을 조합해 가는 듯

근데 이런식으로 돌아가는구나~는 알겠지만 코드는 모르겠음^^;