https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/548/week-5-july-29th-july-31st/3406/

wordBreak2.py

class Trie:
    head = {}
    def add(self, word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        # *가 있을 경우, 그 단어가 자료구조에 저장되어 있음을 의미
        # *가 없을 경우, 그 단어는 자료구조에 저장되어 있지 않음, 단지 더 긴 단어의 부분으로만 존재함
        cur['*'] = True

    def search(self, word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                return False
            cur = cur[ch]

        if '*' in cur:
            return True
        else:
            return False

#dfs
from typing import List
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        trie = Trie()
        for w in wordDict:
            trie.add(w)
        print(wordDict)
        answer = []

        def dfs(remain_str, seq):
            if remain_str == "":
                answer.append(seq[1:])
                return
            else:
                cur = ""
                for i,c in enumerate(remain_str):
                    cur += c
                    if trie.search(cur):
                        dfs(remain_str[i+1:],seq+" "+cur)
        dfs(s,"")


        return answer