3 posts tagged with "Trie"

from typing import Optional


class Node:
    def __init__(self, is_end: bool = False):
        self.is_end = is_end
        self.children: dict[str, Node] = {}

    def __repr__(self):
        return f'''{'! ' if self.is_end else ''}{self.children}'''


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            node.children[c] = node.children.get(c, Node())
            node = node.children[c]
        node.is_end = True

    def _last_node_same_with(self, word: str) -> Optional[Node]:
        node = self.root
        for c in word:
            if c not in node.children:
                return
            node = node.children[c]
        return node

    def search(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node) and node.is_end

    def startsWith(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node)

import heapq
from collections import Counter


class Solution1:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return [x for x in sorted(c, key=lambda key: (-c[key], key))][:k]


class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return heapq.nsmallest(k, c, key=lambda key: (-c[key], key))

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        result = []
        for i, c in enumerate(strs[0]):
            if not all([i < len(s) and c == s[i] for s in strs]):
                break
            result.append(c)
        return ''.join(result)