Advertisement
EWTD

Trie

Jan 5th, 2021
940
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement