FilesExpand file tree

master

/

autocomplete_using_trie.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (53 loc) · 1.51 KB

master

/

autocomplete_using_trie.py

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (53 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

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():

if c == END:

sub_result = [" "]

else:

sub_result = [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()