leetcode

commit ad38e7fa47b37eb6812012b161450d1cb491ed96
parent 474a0b7635ce3991eb3ff06b2a99a0b940afa87b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 27 Mar 2024 14:05:46 +0000

1 Random Problem

Diffstat:
A
Problems/0720.cpp
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 46 insertions(+), 0 deletions(-)
diff --git a/Problems/0720.cpp b/Problems/0720.cpp
@@ -0,0 +1,45 @@
+class Solution {
+    struct Node {
+        Node *children[26] = {0};
+        bool term = false;
+
+        void insert(const string &s) {
+            Node *crnt = this;
+            for (int i = 0; i < size(s); i++) {
+                const int idx = s[i] - 'a';
+                if (!crnt->children[idx]) crnt->children[idx] = new Node();
+                crnt = crnt->children[idx];
+            }
+            crnt->term = true;
+        }
+
+        bool check(const string &s) const {
+            const Node *crnt = this;
+            for (int i = 0; i < size(s); i++) {
+                const int idx = s[i] - 'a';
+                if (!crnt->children[idx]) return false;
+                crnt = crnt->children[idx];
+                if (!crnt->term) return false;
+            }
+            return true;
+        }
+    };
+
+  public:
+    string longestWord(const vector<string> &words) const {
+        Node trie;
+        string res;
+
+        for (const auto &word : words)
+            trie.insert(word);
+        for (const auto &word : words) {
+            if (!trie.check(word)) continue;
+            if (size(word) > size(res))
+                res = word;
+            else if (size(word) == size(res))
+                res = min(res, word);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -453,6 +453,7 @@ for solving problems.
 |  0712  |   Medium   | [Minimum ASCII Delete Sum for Two Strings](Problems/0712.cpp)                                      |
 |  0713  |   Medium   | [Subarray Product Less Than K](Problems/0713.cpp)                                                  |
 |  0714  |   Medium   | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp)                          |
+|  0720  |   Medium   | [Longest Word in Dictionary](Problems/0720.cpp)                                                    |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                              |
 |  0725  |   Medium   | [Split Linked List in Parts](Problems/0725.cpp)                                                    |
 |  0729  |   Medium   | [My Calendar I](Problems/0729.cpp)                                                                 |