208. 实现 Trie (前缀树)

image.png

使用静态链表实现的前缀树在leetcode上空间和时间都用的比较多，因为不太方便将大数组初始化

  1. class Trie {
  2. public:
  3.     Trie() {
  4.         const int N = 100010;
  5.         son = vector<vector<int>>(N, vector<int>(26, 0));
  6.         cnt = vector<int>(N, 0);
  7.     }
  9.     void insert(string word) {
  10.         int cur = 0;
  11.         for (auto ch : word) {
  12.             ch -= 'a';
  13.             if (!son[cur][ch]) son[cur][ch] = ++idx;
  14.             cur = son[cur][ch];
  15.         }
  16.         cnt[cur]++;
  17.     }
  19.     bool search(string word) {
  20.         int cur = 0;
  21.         for (auto ch : word) {
  22.             ch -= 'a';
  23.             if (!son[cur][ch]) return false;
  24.             cur = son[cur][ch];
  25.         }
  26.         return cnt[cur];
  27.     }
  29.     bool startsWith(string prefix) {
  30.         int cur = 0;
  31.         for (auto ch : prefix) {
  32.             ch -= 'a';
  33.             if (!son[cur][ch]) return false;
  34.             cur = son[cur][ch];
  35.         }
  36.         return true;
  37.     }
  38.     vector<vector<int>> son;
  39.     vector<int> cnt;
  40.     int idx = 0; 
  41. };
  43. /**
  44.  * Your Trie object will be instantiated and called as such:
  45.  * Trie* obj = new Trie();
  46.  * obj->insert(word);
  47.  * bool param_2 = obj->search(word);
  48.  * bool param_3 = obj->startsWith(prefix);
  49.  */