本文共 3613 字，大约阅读时间需要 12 分钟。

LeetCode.jpg

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");

你可以假设所有的输入都是由小写字母 a-z 构成的。

Python3 实现

# @author:leacoder # @des:  实现 Trie (前缀树)class Trie:    def __init__(self):        """        Initialize your data structure here.        """        self.root = {}        self.endofword = "end"    def insert(self, word: str) -> None:        """        Inserts a word into the trie.        """        node = self.root        for char in word:            # dict.setdefault(key, default=None) 如果 key 在 字典中，返回对应的值。            # 如果不在字典中，则插入 key 及设置的默认值 default，并返回 default ，default 默认值为 None。            node = node.setdefault(char,{})                     node[self.endofword] = self.endofword    def search(self, word: str) -> bool:        """        Returns if the word is in the trie.        """        node = self.root        for char in word:            if char not in node:                return False            #node = node[char]            node = node.get(char)        return self.endofword in node            def startsWith(self, prefix: str) -> bool:        """        Returns if there is any word in the trie that starts with the given prefix.        """        node = self.root        for char in prefix:            if char not in node:                return False            #node = node[char]            node = node.get(char)        return True

Java 实现

/* *@author:leacoder *@des:  实现 Trie (前缀树) */class Trie {        public int SIZE = 26;    public TrieNode root;        class TrieNode {                TrieNode(char c){            this.val = c;            this.isWord = false;            this.child = new TrieNode[SIZE];        }                public char val;        public boolean isWord;        public TrieNode[] child ;    }            /** Initialize your data structure here. */    public Trie() {        this.root = new TrieNode(' ');    }        /** Inserts a word into the trie. */    public void insert(String word) {        if(word == null || word.length() == 0) return;        TrieNode node = this.root;        for( int i = 0; i < word.length(); i++ ){            char c = word.charAt(i);            if( node.child[c - 'a'] == null){                node.child[c - 'a'] = new TrieNode(c);            }             node = node.child[c - 'a'];        }        node.isWord = true;            }        /** Returns if the word is in the trie. */    public boolean search(String word) {        TrieNode node = this.root;        for( int i = 0; i < word.length(); i++ ){            char c = word.charAt(i);            if( node.child[c - 'a'] == null){                return false;            }            node = node.child[c - 'a'];        }                return node.isWord;    }        /** Returns if there is any word in the trie that starts with the given prefix. */    public boolean startsWith(String prefix) {                TrieNode node = this.root;        for( int i = 0; i < prefix.length(); i++ ){            char c = prefix.charAt(i);            if( node.child[c - 'a'] == null){                return false;            }            node = node.child[c - 'a'];        }                return true;    }}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

GitHub链接：

知乎个人首页：

简书个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101490288 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！