[Leetcode208](python):Trie树的基本操作

1. 题目来源

• 分类：字典树
• Leetcode208:Trie树的基本操作

2. 题目描述

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

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

3. 解题思路

根据Trie Tree(字典树/前缀树/单词查找树)对Trie基本结构，查找，插入等性质的描述进行编写。

4. 编程实现

Python

# 构建字典树结点
class TrieNode:
    def __init__(self):
        # isEnd是否为单词结尾
        self.isEnd = False
        # children
        self.next = [None for i in range(26)]
class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for i in range(len(word)):
            #本题目为0-25长度数组是否为None
            if node.next[ord(word[i]) - ord('a')] == None:
                node.next[ord(word[i]) - ord('a')] = TrieNode()
            node = node.next[ord(word[i]) - ord('a')]
        node.isEnd = True
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for i in range(len(word)):
            if node.next[ord(word[i]) - ord('a')] == None:
                return False
            node = node.next[ord(word[i]) - ord('a')]
        # 确认为单词结束还是只是某个单词前缀
        return node.isEnd

    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 i in range(len(prefix)):
            if node.next[ord(prefix[i]) - ord('a')] == None:
                return False
            node = node.next[ord(prefix[i]) - ord('a')]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)