Leetcode/problem140.py at master · Yuchen112211/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        trie = {}
        _end = '__end__'
        for word in wordDict:
            root = trie
            for character in word:
                root = root.setdefault(character, {})
            root[_end]  = 'end'

        self.ans = []

        def backtrack(string, trie, path):
            if string in wordDict:
                self.ans.append(path + ' ' + string.strip())
            if string == '':
                self.ans.append(path.strip())
            root = trie
            for index in range(len(string)):
                character = string[index]
                if character not in root:
                    return
                root = root[character]
                if _end in root:
                    backtrack(string[index+1:], trie, path + ' ' + string[:index+1])

        backtrack(s, trie, '')

        self.ans = [i.strip() for i in self.ans]
        return set(self.ans)

S = Solution()
s = "aaaaaaa"
wordDict = ["aaaa","aa", "a"]
print S.wordBreak(s,wordDict)