208. 实现 Trie (前缀树) [medium]

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

实现一个 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 构成的。
保证所有输入均为非空字符串。

通过次数45,315 | 提交次数66,717

Second Try

2020-07-22

更标准一点的写法，每次关注的是node，而不是keys，就能够及时判断mark的状态了,也不用像first try里拧巴的使用last node的写法。

class Node:
    def __init__(self):
        self.keys = [None] * 26
        self.mark = False 

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.node = Node() 

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.node 
        for i in range(len(word)):
            idx = ord(word[i]) - ord("a")
            if node.keys[idx] == None:
                node.keys[idx] = Node()
            node = node.keys[idx]
        node.mark = True
            
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.node 
        for i in range(len(word)):
            idx = ord(word[i]) - ord("a")
            if node.keys[idx] == None:
                return False 
            node = node.keys[idx]
        return node.mark 

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        def rec(node):
            """从当前node出发，找到一个mark就算存在"""
            if node.mark:
                return True 
            for k in node.keys:
                if k and rec(k):
                    return True 
            return False 

        node = self.node 
        for c in prefix:
            idx = ord(c) - ord("a")
            if node.keys[idx] is None:
                return False 
            node = node.keys[idx]
        # 其实判断node是否所有keys都为None即可，但还是想查找一遍找到被mark的标记
        return rec(node)

First Try

2020-07-21

隐约记得trie树的keys是按照列表来展开的，终点需要用mark来标记，因此每个节点自然就是一个包含一个26长度的列表和一个mark的Node节点。

不过如果要删除要怎么操作，大量的展开list需要回收吗，一路需要标记什么状态吗，比如后面有多少个word? 看了题解，并没有，只有最后一个isEnd标记而已，写法思路跟我基本一样。

class Node:
    def __init__(self):
        self.keys = [None] * 26
        self.mark = False 

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keys = [None] * 26 

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        keys = self.keys
        for i in range(len(word)):
            idx = ord(word[i]) - ord("a")
            if keys[idx] == None:
                keys[idx] = Node()
            if i == len(word) - 1:
                keys[idx].mark = 2
            keys = keys[idx].keys
            
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        keys = self.keys
        for i in range(len(word)):
            idx = ord(word[i]) - ord("a")
            if keys[idx] == None:
                return False 
            if i == len(word) - 1:
                return keys[idx].mark == 2
            keys = keys[idx].keys
        return False 

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        def rec(node):
            if node.mark == 2:
                return True 
            for k in node.keys:
                if k and rec(k):
                    return True 
            return False 

        keys = self.keys 
        for c in prefix:
            idx = ord(c) - ord("a")
            if keys[idx] is None:
                return False 
            node = keys[idx]
            keys = node.keys
        return rec(node)

        
# 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)

执行用时：276 ms, 在所有 Python3 提交中击败了18.13%的用户
内存消耗：33.3 MB, 在所有 Python3 提交中击败了10.00%的用户

208. 实现 Trie (前缀树) [medium]​

Second Try​

First Try​

208. 实现 Trie (前缀树) [medium]

Second Try

First Try