EWTD

Trie

Jan 5th, 2021
588
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Trie {
  2. public:
  3.     struct Node{
  4.         Node(char _value='-', bool _is_end = false){
  5.             value = _value;
  6.             is_end = _is_end;
  7.             letters.resize(26,nullptr);
  8.         }
  9.         char value;
  10.         vector<Node*> letters;
  11.         bool is_end;
  12.     };
  13.     Node* root;
  14.     /** Initialize your data structure here. */
  15.     Trie() {
  16.         root = new Node();
  17.     }
  18.  
  19.     /** Inserts a word into the trie. */
  20.     void insert(string word) {
  21.         Node* cur = root;
  22.         int i = 0;
  23.         bool flag = true;
  24.         for(; i < word.size(); ++i){
  25.             if(cur->letters[word[i]-'a']){
  26.                 cur = cur->letters[word[i]-'a'];
  27.             }else{
  28.                 flag = false;
  29.                 break;
  30.             }
  31.         }
  32.         if(flag){
  33.             if(!cur->is_end){
  34.                 cur->is_end = true;
  35.             }
  36.         }else{
  37.             for(;i < word.size(); ++i){
  38.                 Node* new_node = new Node(word[i]);
  39.                 cur->letters[word[i]-'a'] = new_node;
  40.                 cur = new_node;
  41.             }
  42.             cur->is_end = true;
  43.         }
  44.     }
  45.  
  46.     /** Returns if the word is in the trie. */
  47.     bool search(string word) {
  48.         Node* cur = root;
  49.         for(int i = 0; i < word.size(); ++i){
  50.             if(cur->letters[word[i]-'a']){
  51.                 cur = cur->letters[word[i]-'a'];
  52.             }else{
  53.                 return false;
  54.             }
  55.         }
  56.         return cur->is_end;
  57.     }
  58.  
  59.     /** Returns if there is any word in the trie that starts with the given prefix. */
  60.     bool startsWith(string prefix) {
  61.         Node* cur = root;
  62.         for(int i = 0; i < prefix.size(); ++i){
  63.             if(cur->letters[prefix[i]-'a']){
  64.                 cur = cur->letters[prefix[i]-'a'];
  65.             }else{
  66.                 return false;
  67.             }
  68.         }
  69.         return true;
  70.     }
  71. };
  72.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×