leetcode

commit c0d745cf4ad9d43b0a2fae08ee9c271d48e69755
parent cef25805b9150a9a2d0e541305df8f8cac80ddcd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 25 Sep 2024 22:57:38 +0200

Daily Problem

Diffstat:
M
Problems/2418.cpp
 | 
47
++++++++++++++++++++++++++++++++++++++---------
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 9 deletions(-)
diff --git a/Problems/2418.cpp b/Problems/2418.cpp
@@ -1,16 +1,45 @@
 class Solution {
-  public:
-    vector<string> sortPeople(vector<string> &names, vector<int> &heights) const {
-        static int idxes[1001];
-        const int n = size(names);
+    class Trie {
+        struct Node {
+            Node *children[26] = {nullptr};
+            int count = 0;
+        } node;
+
+      public:
+        void insert(const string &word) {
+            Node *crnt = &node;
+
+            for (const char c : word) {
+                const auto idx = c - 'a';
+                if (!crnt->children[idx]) crnt->children[idx] = new Node();
+                crnt = crnt->children[idx];
+                crnt->count++;
+            }
+        }
 
-        iota(idxes, idxes + n, 0);
-        sort(idxes, idxes + n, [&](int a, int b) { return heights[a] > heights[b]; });
+        int count(const string &word) const {
+            const Node *crnt = &node;
+            int res = 0;
 
-        vector<string> res(n);
-        for (int i = 0; i < n; i++) {
-            res[i] = names[idxes[i]];
+            for (const char c : word) {
+                const auto idx = c - 'a';
+                crnt = crnt->children[idx];
+                res += crnt->count;
+            }
+
+            return res;
         }
+    };
+
+  public:
+    vector<int> sumPrefixScores(const vector<string> &words) const {
+        vector<int> res;
+        Trie trie;
+
+        for (const auto &word : words)
+            trie.insert(word);
+        for (const auto &word : words)
+            res.push_back(trie.count(word));
 
         return res;
     }
diff --git a/README.md b/README.md
@@ -1204,6 +1204,7 @@ for solving problems.
 |  2410  |   Medium   | [Maximum Matching of Players With Trainers](Problems/2410.cpp)                                     |
 |  2414  |   Medium   | [Length of the Longest Alphabetical Continuous Substring](Problems/2414.cpp)                       |
 |  2415  |   Medium   | [Reverse Odd Levels of Binary Tree](Problems/2415.cpp)                                             |
+|  2416  |    Hard    | [Sum of Prefix Scores of Strings](Problems/2416.cpp)                                               |
 |  2418  |    Easy    | [Sort the People](Problems/2418.cpp)                                                               |
 |  2419  |   Medium   | [Longest Subarray With Maximum Bitwise AND](Problems/2419.cpp)                                     |
 |  2421  |   Medium   | [Number of Good Paths](Problems/2421.cpp)                                                          |