Trie, LetterDict

# DONE

# Trie is implemented as manually nested LetterDict's, factors out common code from `search` and `startsWith` into method `_search`,
# Note: `Trie.END` must be
#   - a character greater than 'z' for correctness
#   - must specifically be `chr(ord('z') + 1)` for time and space efficiency or if using the "Sparse" version of `LetterDict`

# # The "Compact" version of `LetterDict`
# class LetterDict:
#     '''A dicitionary whose keys must be lowercase letters [a-z].'''
#     ORD_a = ord('a')
#     def __init__(self):
#         self.K = 0b0 # keys are lowercase letters [a-z]
#         self.V = [] # values can be anything
#     def __contains__(self, key: str) -> bool:
#         o = ord(key) - self.ORD_a
#         return self.K & (1 << o)
#     def __getitem__(self, key: str):
#         present, i = self.__i(key)
#         if present:
#             return self.V[i]
#         raise KeyError(key)
#     def __setitem__(self, key: str, val):
#         present, i = self.__i(key)
#         if present:
#             self.V[i] = val
#         else:
#             self.V.insert(i, val)
#     def setdefault(self, key: str, defval=None):
#         present, i = self.__i(key)
#         if present:
#             return self.V[i]
#         self.V.insert(i, defval)
#         return defval
#     # SIDE EFFECT: Modifies self.K
#     # As such, __contains__ should not call this method
#     def __i(self, key: str) -> tuple[bool, int]:
#         o = ord(key) - self.ORD_a
#         target = 1 << o
#         present = self.K & target
#         self.K |= target
#         K = self.K
#         i = 0
#         while (K := K & (K - 1)) & target:
#             i += 1
#         return present, i

# The "Sparse" version of `LetterDict`
class LetterDict:
    '''A dicitionary whose keys must be lowercase letters [a-z].'''
    NUM_LETTERS = 26 + 1 # + 1 to accomoated Trie.END = chr(ord('z') + 1)
    EMPTY_VALUE = object() # Cannot be `None` because `None` is a possible value
    ORD_a = ord('a')
    def __init__(self):
        self.K = 0b0 # keys are lowercase letters [a-z]
        self.V = [self.EMPTY_VALUE] * self.NUM_LETTERS  # values can be anything
    def __contains__(self, key: str) -> bool:
        o = ord(key) - self.ORD_a
        return self.V[o] != self.EMPTY_VALUE
    def __getitem__(self, key: str):
        o = ord(key) - self.ORD_a
        if (val := self.V[o]) == self.EMPTY_VALUE:
            raise KeyError(key)
        return val
    def __setitem__(self, key: str, val):
        o = ord(key) - self.ORD_a
        self.V[o] = val
    def setdefault(self, key: str, defval=None):
        o = ord(key) - self.ORD_a
        if (val := self.V[o]) == self.EMPTY_VALUE:
            self.V[o] = defval
            return defval
        return val


class Trie:

    END = chr(ord('z') + 1)

    def __init__(self):
        self.root = LetterDict()


    def insert(self, W: str) -> None:

        # Alt 1
        node = self.root
        for ch in W:
            node = node.setdefault(ch, LetterDict())
        node[self.END] = None

        # # Alt 2
        # node = self.root
        # for ch in W:
        #     if ch not in node:
        #         node[ch] = LetterDict()
        #     node = node[ch]
        # node[self.END] = None

        # # Alt 3
        # reduce(lambda node, ch: node.setdefault(ch, LetterDict()), W, self.root)[self.END] = None


    def search(self, W: str) -> bool:
        return self._search(W)


    def startsWith(self, P: str) -> bool:
        return self._search(P, isPrefix=True)


    def _search(self, W: str, isPrefix: bool=False) -> bool:
        node = self.root
        for ch in W:
            if ch not in node:
                return False
            node = node[ch]
        return isPrefix or self.END in node




# # Manually nested dictionaries, factors out common code from `search` and `startsWith` into method `_search`.
# class Trie:

#     END = '$'

#     def __init__(self):
#         self.root = {}


#     def insert(self, W: str) -> None:

#         # Alt 1
#         node = self.root
#         for ch in W:
#             node = node.setdefault(ch, {})
#         node[self.END] = None

#         # # Alt 2
#         # node = self.root
#         # for ch in W:
#             # if ch not in node:
#             #     node[ch] = {}
#             # node = node[ch]
#         # node[self.END] = None

#         # # Alt 3
#         # reduce(lambda node, ch: node.setdefault(ch, {}), W, self.root)[self.END] = None


#     def search(self, W: str) -> bool:
#         return self._search(W)


#     def startsWith(self, P: str) -> bool:
#         return self._search(P, isPrefix=True)


#     def _search(self, W: str, isPrefix: bool=False) -> bool:
#         node = self.root
#         for ch in W:
#             if ch not in node:
#                 return False
#             node = node[ch]
#         return isPrefix or self.END in node




# # Manually nested dictionaries
# class Trie:

#     END = '$'

#     def __init__(self):
#         self.root = {}


#     def insert(self, W: str) -> None:

#         # Alt 1
#         node = self.root
#         for ch in W:
#             node = node.setdefault(ch, {})
#         node[self.END] = None

#         # # Alt 2
#         # node = self.root
#         # for ch in W:
#             # if ch not in node:
#             #     node[ch] = {}
#             # node = node[ch]
#         # node[self.END] = None

#         # # Alt 3
#         # reduce(lambda node, ch: node.setdefault(ch, {}), W, self.root)[self.END] = None


#     def search(self, W: str) -> bool:
#         node = self.root
#         for ch in W:
#             if ch not in node:
#                 return False
#             node = node[ch]
#         return self.END in node


#     def startsWith(self, P: str) -> bool:
#         node = self.root
#         for ch in P:
#             if ch not in node:
#                 return False
#             node = node[ch]
#         return True




# # Automatically nested dictionaries via `tree = lambda: defaultdict(tree)`
# # self.root is a defaultdict of defaultdict of defaultdict of ...
# class Trie:

#     END = '$'

#     def __init__(self):
#         tree = lambda: defaultdict(tree)
#         self.root = tree()


#     def insert(self, W: str) -> None:

#         # Alt 1
#         node = self.root
#         for ch in W:
#             node = node[ch]
#         node[self.END] = None

#         # # Alt 2
#         # reduce(dict.__getitem__, W, self.root)[self.END] = None


#     def search(self, W: str) -> bool:
#         node = self.root
#         for ch in W:
#             if ch not in node:
#                 return False
#             node = node[ch]
#         return self.END in node


#     def startsWith(self, P: str) -> bool:
#         node = self.root
#         for ch in P:
#             if ch not in node:
#                 return False
#             node = node[ch]
#         return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)