leetcode

commit 74ba4dea073e7d5284195d863285e4ffe73cbdc8
parent 4d9545c662f598f447e8668e6dc2e40674e74e31
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 20 Sep 2024 18:38:57 +0200

Daily Problem

Diffstat:
A
Problems/0214.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0214.cpp b/Problems/0214.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  public:
+    string shortestPalindrome(const string &s) const {
+        const int n = s.size();
+        int i = 0, j = n - 1;
+
+        while (j >= 0) {
+            if (s[i] == s[j]) i++;
+            j--;
+        }
+
+        if (i == n) return s;
+        string remain = s.substr(i), rev = remain;
+        reverse(rev.begin(), rev.end());
+
+        return rev + shortestPalindrome(s.substr(0, i)) + remain;
+    }
+};
diff --git a/README.md b/README.md
@@ -221,6 +221,7 @@ for solving problems.
 |  0211  |   Medium   | [Design Add and Search Words Data Structure](Problems/0211.cpp)                                    |
 |  0212  |    Hard    | [Word Search II](Problems/0212.cpp)                                                                |
 |  0213  |   Medium   | [House Robber II](Problems/0213.cpp)                                                               |
+|  0214  |    Hard    | [Shortest Palindrome](Problems/0214.cpp)                                                           |
 |  0215  |   Medium   | [Kth Largest Element in an Array](Problems/0215.cpp)                                               |
 |  0216  |   Medium   | [Combination Sum III](Problems/0216.cpp)                                                           |
 |  0217  |    Easy    | [Contains Duplicate](Problems/0217.cpp)                                                            |