LeetCode/472.ConcatenatedWords.py at master · tobyatgithub/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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# class Solution:
#     # 1 - need to fix the cache.
#     # 2 - lru_cache decorator can only be used on hashable objects (i.e. can't be applied on dict)
#     def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
#         def isValid(word, lookup):
#             #             print(f"word = {word}")
#             #             print("cache = ", cache)
#             #             print()

#             #             if word in cache:
#             #                 return cache[word]
#             if word in res:
#                 return True

#             if len(word) == 0:
#                 return True
#             first_letter = word[0]
#             for candidate in lookup[first_letter]:
#                 if candidate == word[: len(candidate)] and isValid(
#                     word[len(candidate) :], lookup
#                 ):
#                     cache[word] = True
#                     return True
#             # cache[word] = False
#             return False

#         cache = {}
#         from collections import defaultdict

#         lookup = defaultdict(set)
#         # form
#         for word in words:
#             if len(word) == 0:
#                 continue
#             lookup[word[0]].add(word)  # key: first letter, value: word

#         res = []
#         for word in words:
#             if len(word) == 0:
#                 continue
#             lookup[word[0]].remove(word)
#             if isValid(word, lookup):
#                 res.append(word)
#             lookup[word[0]].add(word)
#         return res


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        cache = {}
        from collections import defaultdict

        lookup = defaultdict(set)

        # form
        for word in words:
            if len(word) == 0:
                continue

            if word[0] not in lookup:
                lookup[word[0]] = set()
            lookup[word[0]].add(word)  # key: first letter, value: word

        def isValid(word, lookup):
            nonlocal cache
            if word in cache:
                return cache[word]

            if len(word) == 0:
                return True
            first_letter = word[0]
            for candidate in lookup[first_letter]:
                if candidate == word[: len(candidate)] and isValid(
                    word[len(candidate) :], lookup
                ):
                    cache[word] = True
                    return True
            return False

        res = []
        for word in words:
            if len(word) == 0:
                continue
            lookup[word[0]].remove(word)
            if isValid(word, lookup):
                res.append(word)
            print(f"word = {word}")
            print("res = ", res)
            print("cache = ", cache)
            print()

            lookup[word[0]].add(word)

        return res