Trie Implementation: Prefix Trees for Efficient String Operations

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_word = False    # End of word
        self.count = 0           # Number of words with this prefix

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1
        node.is_word = True
    
    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_word
    
    def starts_with(self, prefix):
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
    
    def delete(self, word):
        self._delete(self.root, word, 0)
    
    def _delete(self, node, word, depth):
        if depth == len(word):
            if node.is_word:
                node.is_word = False
            return node.children == {}
        
        char = word[depth]
        if char not in node.children:
            return False
        
        child = node.children[char]
        should_delete_child = self._delete(child, word, depth + 1)
        
        if should_delete_child:
            del node.children[char]
            return node.children == {}
        
        return False

class TrieWithCount:
    def __init__(self):
        self.root = {
            'children': {},
            'is_word': False,
            'word_count': 0  # Words ending at this node
        }
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node['children']:
                node['children'][char] = {
                    'children': {},
                    'is_word': False,
                    'word_count': 0
                }
            node = node['children'][char]
        node['is_word'] = True
        node['word_count'] += 1
    
    def count_words_equal_to(self, word):
        node = self._find_node(word)
        return node['word_count'] if node else 0
    
    def count_words_starting_with(self, prefix):
        node = self._find_node(prefix)
        return self._count_all(node)
    
    def _count_all(self, node):
        if not node:
            return 0
        count = node['word_count']
        for child in node['children'].values():
            count += self._count_all(child)
        return count
    
    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node['children']:
                return None
            node = node['children'][char]
        return node

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.trie = TrieWithCount()
        
        for sentence, count in zip(sentences, times):
            # Add multiple times
            for _ in range(count):
                self.trie.insert(sentence)
        
        self.current = ""
    
    def input(self, c):
        if c == '#':
            # Reset
            self.trie.insert(self.current)
            self.current = ""
            return []
        
        self.current += c
        
        # Get top 3 suggestions
        suggestions = []
        self._find_top(self.trie.root, self.current, suggestions, [])
        
        return [''.join(s) for s in suggestions[:3]]
    
    def _find_top(self, node, prefix, suggestions, current):
        if len(suggestions) >= 3:
            return
        
        if node['is_word']:
            suggestions.append((node['word_count'], current[:]))
        
        for char, child in sorted(node['children'].items()):
            current.append(char)
            self._find_top(child, prefix, suggestions, current)
            current.pop()
    
    # Sort by count
    suggestions.sort(key=lambda x: -x[0])

def longest_common_prefix(strings):
    if not strings:
        return ""
    
    # Find minimum length
    min_len = min(len(s) for s in strings)
    
    # Compare character by character
    result = ""
    for i in range(min_len):
        char = strings[0][i]
        if all(s[i] == char for s in strings):
            result += char
        else:
            break
    
    return result


# Using Trie
def longest_prefix(trie):
    prefix = ""
    node = trie.root
    
    # While single path
    while (len(node.children) == 1 and 
           not node.is_word):
        char = list(node.children.keys())[0]
        prefix += char
        node = node.children[char]
    
    return prefix

def find_words(board, words):
    """Find all words from board using Trie"""
    
    # Build Trie from words
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    result = set()
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, node, path):
        char = board[r][c]
        
        if char not in node.children:
            return
        
        next_node = node.children[char]
        path.append(char)
        
        if next_node.is_word:
            result.add(''.join(path))
        
        # Mark visited
        board[r][c] = '#'
        
        # Explore neighbors
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                dfs(nr, nc, next_node, path)
        
        # Backtrack
        board[r][c] = char
        path.pop()
    
    # Start DFS from each cell
    for i in range(rows):
        for j in range(cols):
            if board[i][j] in trie.root.children:
                dfs(i, j, trie.root, [])
    
    return list(result)

def replace_words(dict, sentence):
    """Replace words with shortest root"""
    trie = Trie()
    
    for word in dict:
        trie.insert(word)
    
    result = []
    
    for word in sentence.split():
        prefix = ""
        node = trie.root
        
        for char in word:
            if char not in node.children:
                break
            prefix += char
            node = node.children[char]
            if node.is_word:
                break
        
        result.append(prefix if node.is_word else word)
    
    return ' '.join(result)

class TrieNode:
    def __init__(self, char):
        self.char = char
        self.left = None    # ASCII < char
        self.mid = None    # ASCII == char
        self.right = None  # ASCII > char
        self.is_word = False


class TernarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, word):
        self.root = self._insert(self.root, word, 0)
    
    def _insert(self, node, word, index):
        if index == len(word):
            node.is_word = True
            return node
        
        char = word[index]
        
        if not node:
            node = TrieNode(char)
        
        if char < node.char:
            node.left = self._insert(node.left, word, index)
        elif char > node.char:
            node.right = self._insert(node.right, word, index)
        else:
            node.mid = self._insert(node.mid, word, index + 1)
        
        return node
    
    def search(self, word):
        return self._search(self.root, word, 0)
    
    def _search(self, node, word, index):
        if not node:
            return False
        
        char = word[index]
        
        if char < node.char:
            return self._search(node.left, word, index)
        elif char > node.char:
            return self._search(node.right, word, index)
        else:
            if index == len(word) - 1:
                return node.is_word
            return self._search(node.mid, word, index + 1)

# Trie complexity

complexity = {
    "insert": "O(m) where m = word length",
    "search": "O(m)",
    "starts_with": "O(m)",
    "space": "O(ALPHABET_SIZE × m × n)",
    
    "vs_hash_table": {
        "insert": "Same O(m)",
        "search": "Same O(m)",
        "prefix": "O(1) vs O(m)",
        "space": "More efficient for prefixes"
    }
}