1
# Runtime: 56 ms (Top 49.21%) | Memory: 14 MB (Top 33.37%)
2
class Solution(object):
3
    def wordBreak(self, s, wordDict):
4
        """
5
        :type s: str
6
        :type wordDict: List[str]
7
        :rtype: List[str]
8
        """
9

10
        dic = defaultdict(list)
11
        for w in wordDict:
12
            dic[w[0]].append(w)
13
        result = []
14

15
        def recursion(idx, ans):
16
            if idx >= len(s):
17
                result.append(" ".join(ans))
18
                return
19

20
            for w in dic[s[idx]]:
21
                if s[idx : idx + len(w)] == w:
22
                    ans.append(w)
23
                    recursion(idx + len(w), ans)
24
                    ans.pop()
25

26
            return
27

28
        recursion(0, [])
29
        return result