leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0208.cpp (936B)

      1 class Trie {
      2     struct Record {
      3         bool end;
      4         array<Record *, 26> records = {nullptr};
      5 
      6         Record *insert(int x) {
      7             if (records[x]) return records[x];
      8             return records[x] = new Record();
      9         }
     10 
     11         Record *check(int x) { return records[x]; }
     12     };
     13 
     14     Record *record = new Record;
     15     Record *last(string word) {
     16         Record *crnt = record;
     17         for (char c : word)
     18             if (!crnt)
     19                 return nullptr;
     20             else
     21                 crnt = crnt->check(c - 'a');
     22         return crnt;
     23     }
     24 
     25   public:
     26     void insert(string word) {
     27         Record *crnt = record;
     28         for (char c : word)
     29             crnt = crnt->insert(c - 'a');
     30         crnt->end = true;
     31     }
     32 
     33     bool search(string word) {
     34         Record *crnt = last(word);
     35         if (!crnt) return false;
     36         return crnt->end;
     37     }
     38 
     39     bool startsWith(string prefix) { return last(prefix); }
     40 };