Search Implementations

Trie (Prefix Tree)

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True

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

Inverted Index

def build_index(docs: list[str]) -> dict[str, list[int]]:
    index = {}
    for doc_id, text in enumerate(docs):
        for word in text.lower().split():
            index.setdefault(word, []).append(doc_id)
    return index