Leetcode 208:实现 Trie (前缀树)(超详细解决方案!!!)
in leetcode with 0 comment

Leetcode 208:实现 Trie (前缀树)(超详细解决方案!!!)

in leetcode with 0 comment

实现一个 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

说明:

解题思路

很基础的问题,考察基础概念。

class Node:
    def __init__(self, isWord=False):
        self.isWord = isWord
        self.next = dict()
        
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.next:    # here
                cur.next[c] = Node()
            cur = cur.next[c]
            
        if not cur.isWord:
            cur.isWord = True
        
    def search(self, word):
        cur = self._search(word)
        return cur != None and cur.isWord
        
    def _search(self, word):
        cur = self.root
        for c in word:
            cur = cur.next.get(c, None)
            if not cur:
                return None
        return cur
        
    def startsWith(self, prefix):
        return self._search(prefix) != None 

还可以使用defaultdict实现,不过需要注意一些细节问题。

class Node:
    def __init__(self, isWord=False):
        self.isWord = isWord
        self.next = collections.defaultdict(Node)
        
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        cur = self.root
        for c in word:
            cur = cur.next[c]    # here
            
        if not cur.isWord:
            cur.isWord = True
        
    def search(self, word):
        cur = self._search(word)
        return cur != None and cur.isWord
        
    def _search(self, word):
        cur = self.root
        for c in word:
            cur = cur.next.get(c)
            if not cur:
                return None
        return cur
        
    def startsWith(self, prefix):
        return self._search(prefix) != None

注意上面代码写法中的标记位置here,通过defaultdict话可以自动构建连接关系,而不需要手动创建。另外,在使用cpp实现的时候不要漏掉析构函数

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses