输入提示数据算法 Trie

向右看齐 2022-10-14 12:54 109阅读 0赞

### 基本功能 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaV9ib19jYWk_size_16_color_FFFFFF_t_70_pic_center]

1.  实现上述功能，输入提示
2.  数据结构：`Trie` 字典树 多叉树 根节点为空值
3.  缺点：数据要求比较高，会占用大量的空间。例如：26个字母，组成完全的 `Trie`树的话，就会有26层，总共有`26的26次方`个节点
4.  不仅仅可以实现这种功能，类似于有共同前缀的数据，也可以 以这种方式实现

### 实现代码 ###

from copy import deepcopy
    from collections.abc import Iterable
    from collections import defaultdict
    
    
    class Trie:
        def __init__(self, nodes: Iterable):
            """
    
            :param nodes: list or str，可以为一个多个节点或是一个节点
            """
            self.tree = defaultdict(dict)
            self.depth = 0
            self.init_tree(nodes)
    
        def insert_node(self, i, node, len_node, tree):
            """
            插入元素
            :param i: 元素的第几个字符
            :param node: 元素
            :param len_node: 元素长度
            :param tree: 树结构
            :return:
            """
            if node[i] in tree:
                self.insert_node(i + 1, node, len_node, tree[node[i]])
            else:
                tree[node[i]] = defaultdict(dict)
                if len_node > i + 1:
                    self.insert_node(i + 1, node, len_node, tree[node[i]])
    
        def init_tree(self, nodes):
            """
            插入元素
            :param nodes: 可迭代对象，对应要插入的元素
            :return:
            """
            if isinstance(nodes, Iterable):
                for node in nodes:
                    len_node = len(node)
                    if len_node > self.depth:
                        self.depth = len_node
                    self.insert_node(0, node, len_node, self.tree)
            else:
                raise ValueError
    
        def get_level(self, c_tree: dict, result: list, add_signal, path=None):
            """
            获取需要新添加的数据
            :param c_tree: 原始数据
            :param result: 结果
            :param path:
            :param add_signal: 需要添加到结果的条件
            :return:
            """
            if path is None:
                path = []
            for k, v in c_tree.items():
                path_new = deepcopy(path)
                path_new.append(k)
                if add_signal(k, v):
                    result.append(path_new)
                if v:
                    self.get_level(v, result, add_signal, path=path_new)
    
        def __find_word(self, i, node, len_node, tree):
            if node[i] in tree:
                if i + 1 < len_node:
                    tree = self.__find_word(i + 1, node, len_node, tree[node[i]])
                return tree
    
        def find_word(self, word):
            """
            获取提示
            """
            len_word = len(word)
            if len_word > self.depth:
                return [word]
            last_tree = self.__find_word(0, word, len_word, self.tree)
            if last_tree is None:
                return []
            result = list()
            self.get_level(last_tree[word[-1]], result, lambda k, v: not v)
            return [word + ''.join(r) for r in result]
    
    
    if __name__ == '__main__':
        trie = Trie(['hello', 'her', 'hi', 'how', 'so', 'see', 'some', 'solr'])
        print(trie.find_word('s'))
        print(trie.find_word('so'))
        print(trie.find_word('som'))
        print(trie.find_word('some'))
        print(trie.find_word('something'))
        print(trie.find_word('y'))
    
        trie = Trie([('中国', '北京', '海淀'), ('美国', '华盛顿', '特区')])

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaV9ib19jYWk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/915a2091993a45fe909e3757b68498ab.png