【每日演算法Day 84】面試必考題：Trie（字典樹/前綴樹）的實現

2020 年 4 月 2 日
筆記

題目鏈接

LeetCode 208. 實現 Trie (前綴樹)[1]

題目描述

實現一個 Trie （前綴樹），包含 insert, search, 和 startsWith 這三個操作。

示例1

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

說明：

你可以假設所有的輸入都是由小寫字母構成的。
保證所有輸入均為非空字元串。

題解

字典樹主要支援插入字元串、查詢字元串是否在字典樹中、查詢字典樹中是否存在某個前綴等操作，我這裡還額外實現了一下 c++ 版本的刪除字元串操作。

初始化字典樹

初始化的時候，根結點為空，不用來放任何字元，所有字元串都是從下一層子結點開始存儲。

每個結點有 26 個指針，指向下一層子結點，每個指針代表著下一個不同的字母。

每個結點還保存了一個變數 isEnd ，用來表示該結點是不是某個字元串結束的位置。

插入字元串

從根結點往下遞歸，如果字元串中下一個字母對應的子結點為空，那就新建一個結點再遞歸，否則的話就直接遞歸下去。

最後把最後一個結點的 isEnd 設置為 1，表示這個結點是字元串的結束位置。

查詢字元串

從根結點往下遞歸查找，如果字元串還沒遍歷結束，但是結點已經空了，說明字元串不在字典樹中。否則的話一直查找到最後一個字元，然後看對應結點的 isEnd 是 1 還是 0，如果是 1 ，就存在字元串，否則不存在。

查詢字元串前綴

和查詢字元串過程一模一樣，唯一的區別就是最後不用看最後一個結點的 isEnd 了，直接返回 true 。因為既然都查詢到了最後一個字元了，說明這個前綴一定存在。

刪除字元串

這個是我自己實現的，一般來說字典樹很少用到刪除操作。

首先整體框架是和查詢字元串類似的，從根結點往下遞歸查詢，然後用一個棧保存查詢到的結點。

如果查詢過程中直接遇到了空結點，就直接返回，因為都不存在字元串，就不用刪除了。然後判斷最後一個結點的類型。

如果它的 isEnd 是 0，說明字元串不存在，那就直接返回不用刪了。

如果它不是葉子結點，說明後面還接著字元串呢，那也不用刪了，只要把該結點的 isEnd 設置為 0 就行了。

否則的話它就是葉子結點，那麼就直接刪除這個結點，並且從棧里出棧。

然後從棧里最後一個結點開始刪除，直到棧頂的結點不是葉子結點（表示字典樹中存在刪除字元串的相同前綴字元串）或者 isEnd 是 1（表示字典樹中存在刪除字元串的前綴子串）。

程式碼

具體實現上面，c++ 我採用的結構體指針來構建出了一顆樹。而 python 我直接用的嵌套的字典，並沒有真正的構建出樹，只有一個類，這樣還挺方便的，但是刪除操作有點麻煩，暫時就不寫了。

c++

class Trie {  public:      bool isEnd;      vector<Trie*> next;        Trie() {          isEnd = false;          next = vector<Trie*>(26, 0);      }        ~Trie() {          for (auto p : next) delete p;      }        void insert(string word) {          Trie* node = this;          for (auto c : word) {              if (node->next[c-'a'] == NULL) {                  node->next[c-'a'] = new Trie();              }              node = node->next[c-'a'];          }          node->isEnd = true;      }        void del(string word) {          stack<Trie*> st;          Trie* node = this;          for (auto c : word) {              node = node->next[c-'a'];              st.push(node);              if (node == NULL) return;          }          if (!(node->isEnd)) return;          if (!isLeaf(node)) {              node->isEnd = false;              return;          }          delete node;          st.pop();          while (!st.empty()) {              node = st.top();              st.pop();              if (isLeaf(node) && !(node->isEnd)) delete node;              else break;          }      }        bool search(string word) {          Trie* node = this;          for (auto c : word) {              node = node->next[c-'a'];              if (node == NULL) return false;          }          return node->isEnd;      }        bool startsWith(string prefix) {          Trie* node = this;          for (auto c : prefix) {              node = node->next[c-'a'];              if (node == NULL) return false;          }          return true;      }        bool isLeaf(Trie* node) {          for (auto p : next) {              if (p) return false;          }          return true;      }  };

python

class Trie:      def __init__(self):          self.nxt = {}        def insert(self, word: str) -> None:          node = self.nxt          for c in word:              if c not in node:                  node[c] = {}              node = node[c]          node['#'] = True        def search(self, word: str) -> bool:          node = self.nxt          for c in word:              if c not in node:                  return False              node = node[c]          return '#' in node        def startsWith(self, prefix: str) -> bool:          node = self.nxt          for c in prefix:              if c not in node:                  return False              node = node[c]          return True

參考資料

[1]

LeetCode 208. 實現 Trie (前綴樹): https://leetcode-cn.com/problems/implement-trie-prefix-tree/

作者簡介：godweiyang，知乎同名，華東師範大學電腦系碩士在讀，方向自然語言處理與深度學習。喜歡與人分享技術與知識，期待與你的進一步交流~