题目

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

示例:

  1. Trie trie = new Trie();
  3. trie.insert("apple");
  4. trie.search("apple");   // 返回 true
  5. trie.search("app");     // 返回 false
  6. trie.startsWith("app"); // 返回 true
  7. trie.insert("app");   
  8. trie.search("app");     // 返回 true

说明:

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

方案一（数组）

  1. class Node:
  2.     def __init__(self, val):
  3.         self.val = val
  4.         self.is_word = False # 是否是一个词
  5.         self.children = [None] * 26
  7. class Trie:
  9.     def __init__(self):
  10.         """
  11.         Initialize your data structure here.
  12.         """
  13.         self.root = Node(None)        
  16.     def insert(self, word: str) -> None:
  17.         """
  18.         Inserts a word into the trie.
  19.         """
  20.         nodes = self.root.children
  21.         length = len(word)
  22.         for i, c in enumerate(word):
  23.             index = ord(c) - 97 # ord('a') == 97
  24.             if not nodes[index]:
  25.                 nodes[index] = Node(c)
  26.             if i == length - 1:
  27.                 nodes[index].is_word = True
  28.             nodes = nodes[index].children
  31.     def search(self, word: str) -> bool:
  32.         """
  33.         Returns if the word is in the trie.
  34.         """
  35.         nodes = self.root.children
  36.         length = len(word)
  37.         for i, c in enumerate(word):
  38.             index = ord(c) - 97
  39.             if not nodes[index]:
  40.                 return False
  41.             if i == length - 1:
  42.                 if nodes[index].is_word:
  43.                     return True
  44.                 else:
  45.                     return False
  46.             nodes = nodes[index].children
  49.     def startsWith(self, prefix: str) -> bool:
  50.         """
  51.         Returns if there is any word in the trie that starts with the given prefix.
  52.         """
  53.         nodes = self.root.children
  54.         length = len(prefix)
  55.         for i, c in enumerate(prefix):
  56.             index = ord(c) - 97
  57.             if not nodes[index]:
  58.                 return False
  59.             if i == length - 1:
  60.                 return True
  61.             nodes = nodes[index].children

方案二（Map）

  1. class Trie:
  3.     def __init__(self):
  4.         """
  5.         Initialize your data structure here.
  7.         'bed' -> {
  8.             'b': {
  9.                 'e': {
  10.                     'd': {
  11.                         'is_word': True
  12.                     }
  13.                 }
  14.             }
  15.         }
  16.         """
  17.         self.lookup = {}
  20.     def insert(self, word: str) -> None:
  21.         """
  22.         Inserts a word into the trie.
  23.         """
  24.         node = self.lookup
  25.         for c in word:
  26.             if c not in node:
  27.                 node[c] = {}
  28.             node = node[c]
  29.         node['is_word'] = True
  32.     def search(self, word: str) -> bool:
  33.         """
  34.         Returns if the word is in the trie.
  35.         """
  36.         node = self.lookup
  37.         for c in word:
  38.             if c not in node:
  39.                 return False
  40.             node = node[c]
  41.         # 判断是否是单词
  42.         if 'is_word' in node:
  43.             return True
  44.         return False
  47.     def startsWith(self, prefix: str) -> bool:
  48.         """
  49.         Returns if there is any word in the trie that starts with the given prefix.
  50.         """
  51.         node = self.lookup
  52.         for c in prefix:
  53.             if c not in node:
  54.                 return False
  55.             node = node[c]
  56.         return True

原文

https://leetcode-cn.com/explore/learn/card/trie/166/basic-operations/645/