Реализация Trie для поддержки автозаполнения в Python

Question

Я пытаюсь реализовать структуру данных, которая поддерживает автозаполнение на веб-сайте. Мне удалось реализовать итеративную версию Trie. Он поддерживает два основных метода добавления и поиска в Trie. Однако теперь мне нужно добавить метод, который возвращает все слова, начинающиеся со следующего префикса. Может кто-то помочь мне с этим.

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

    def insert(self, word):
        curr = self.root
        for letter in word:
            node = curr.children.get(letter)
            if not node:
                node = TrieNode()
                curr.children[letter] = node
            curr = node
        curr.end = True

    def search(self, word):
        curr = self.root
        for letter in word:
            node = curr.children.get(letter)
            if not node:
                return False
            curr = node
        return curr.end

    def all_words_beginning_with_prefix(self, prefix):
        #I'm not sure how to go about this one.

Answer 1

Вы можете просто реализовать генератор, который перебирает Trie в соответствии с префиксом так же, как и другие методы. Как только вы нашли узел в конце префикса, вы можете использовать рекурсивный генератор с yield from выполнить итерацию по поддереву, сохраняя при этом префикс и получая его при обнаружении терминального узла:

class TrieNode:
    def __init__(self):
        self.end = False
        self.children = {}

    def all_words(self, prefix):
        if self.end:
            yield prefix

        for letter, child in self.children.items():
            yield from child.all_words(prefix + letter)

class Trie:
    # existing methods here
    def all_words_beginning_with_prefix(self, prefix):
        cur = self.root
        for c in prefix:
            cur = cur.children.get(c)
            if cur is None:
                return  # No words with given prefix

        yield from cur.all_words(prefix)

trie = Trie()
trie.insert('foobar')
trie.insert('foo')
trie.insert('bar')
trie.insert('foob')
trie.insert('foof')

print(list(trie.all_words_beginning_with_prefix('foo')))

Выход:

['foo', 'foob', 'foobar', 'foof']

Answer 2

      from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.node = defaultdict(TrieNode)
        self.is_word = False


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

    def insert(self, words):
        curr = self.root

        for char in words:
            curr = curr.node[char]
        curr.is_word = True

    def search(self, word):
        curr = self.root
        for char in word:
            if char not in curr.node:
                return False
            curr = curr.node[char]
        return curr.is_word

    def dfs(self, node, word, word_list):
        if node.is_word == True:
            word_list.append(word)
        for a, n in node.node.items():
            self.dfs(n, word + a, word_list)

    def auto_complete(self, word_to_search, word_list):
        temp_word = ""
        curr = self.root
        for char in word_to_search:
            if char not in curr.node.keys():
                print("Invalid Input")
            else:
                temp_word += char
                curr = curr.node[char]
        self.dfs(curr, temp_word, word_list)
        print(word_list)

Answer 3

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end = "#"

    def words_with_prefix(self, prefix: str):
        '''
        return all possible words with common prefix
        '''
        node = self.root
        for c in prefix:
            if c not in node:
                return []
            node = node[c]
        ans = []
        self._words_with_prefix_helper(node, prefix, ans)
        return ans

    def _words_with_prefix_helper(self, node, prefix, ans):
        for k in node:
            if k == self.end:
                ans.append(prefix)
                continue
            self._words_with_prefix_helper(node[k], prefix + k, ans)

полная реализация