leetcode

commit 465ba507ffa258b00f7a4f31800045f5181fa687
parent c9ad882ab84a9579627a9b1eb7f856f23c3c01e4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 19 Feb 2023 19:56:02 +0100

LeetCode 75 II: Day 16

Diffstat:
A
Problems/0208.cpp
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 40 insertions(+), 0 deletions(-)
diff --git a/Problems/0208.cpp b/Problems/0208.cpp
@@ -0,0 +1,39 @@
+class Trie {
+  struct Record {
+    bool end;
+    array<Record *, 26> records = {nullptr};
+
+    Record *insert(int x) {
+      if (records[x]) return records[x];
+      return records[x] = new Record();
+    }
+
+    Record *check(int x) { return records[x]; }
+  };
+
+  Record *record = new Record;
+  Record *last(string word) {
+    Record *crnt = record;
+    for (char c : word)
+      if (!crnt)
+        return nullptr;
+      else
+        crnt = crnt->check(c - 'a');
+    return crnt;
+  }
+
+public:
+  void insert(string word) {
+    Record *crnt = record;
+    for (char c : word) crnt = crnt->insert(c - 'a');
+    crnt->end = true;
+  }
+
+  bool search(string word) {
+    Record *crnt = last(word);
+    if (!crnt) return false;
+    return crnt->end;
+  }
+
+  bool startsWith(string prefix) { return last(prefix); }
+};
diff --git a/README.md b/README.md
@@ -159,6 +159,7 @@ for solving problems.
 |  0205  |    Easy    | [Isomorphic Strings](Problems/0205.cpp)                                                          |
 |  0206  |    Easy    | [Reverse Linked List](Problems/0206.cpp)                                                         |
 |  0207  |   Medium   | [Course Schedule](Problems/0207.cpp)                                                             |
+|  0208  |   Medium   | [Implement Trie (Prefix Tree)](Problems/0208.cpp)                                                |
 |  0209  |   Medium   | [Minimum Size Subarray Sum](Problems/0209.cpp)                                                   |
 |  0210  |   Medium   | [Course Schedule II](Problems/0210.cpp)                                                          |
 |  0213  |   Medium   | [House Robber II](Problems/0213.cpp)                                                             |