/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
strings/autocomplete_using_trie.py
65 строк
1 KB
Christian Clauss
Make some ruff fixes (#8154)
01 мар 2023, 19:23
Не верифицирован
01 мар 2023, 19:23
64543fa
Код
Авторство
О чём код?
from __future__ import annotations END = "#" class Trie: def __init__(self) -> None: self._trie: dict = {} def insert_word(self, text: str) -> None: trie = self._trie for char in text: if char not in trie: trie[char] = {} trie = trie[char] trie[END] = True def find_word(self, prefix: str) -> tuple | list: trie = self._trie for char in prefix: if char in trie: trie = trie[char] else: return [] return self._elements(trie) def _elements(self, d: dict) -> tuple: result = [] for c, v in d.items(): sub_result = [" "] if c == END else [(c + s) for s in self._elements(v)] result.extend(sub_result) return tuple(result) trie = Trie() words = ("depart", "detergent", "daring", "dog", "deer", "deal") for word in words: trie.insert_word(word) def autocomplete_using_trie(string: str) -> tuple: """ >>> trie = Trie() >>> for word in words: ... trie.insert_word(word) ... >>> matches = autocomplete_using_trie("de") >>> "detergent " in matches True >>> "dog " in matches False """ suffixes = trie.find_word(string) return tuple(string + word for word in suffixes) def main() -> None: print(autocomplete_using_trie("de")) if __name__ == "__main__": import doctest doctest.testmod() main()