leetcode

commit e4884434eca0a56ae251c262f5a482a81572abbe
parent 769fa3ed8f0cdcf3758b5acf2f1a5d40418e052e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 22 Apr 2023 13:32:16 +0200

Daily Problem

Diffstat:
A
Problems/1312.cpp
 | 
13
+++++++++++++
M
README.md
 | 
1
+

2 files changed, 14 insertions(+), 0 deletions(-)
diff --git a/Problems/1312.cpp b/Problems/1312.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+  int minInsertions(string s) {
+    int dp[501][501] = {0}, n = s.size();
+    for (int i = 0; i < n; i++)
+      for (int j = 0; j < n; j++)
+        if (s[i] == s[n - 1 - j])
+          dp[i + 1][j + 1] = dp[i][j] + 1;
+        else
+          dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
+    return n - dp[n][n];
+  }
+};
diff --git a/README.md b/README.md
@@ -413,6 +413,7 @@ for solving problems.
 |  1302  |   Medium   | [Deepest Leaves Sum](Problems/1302.cpp)                                                          |
 |  1305  |   Medium   | [All Elements in Two Binary Search Trees](Problems/1305.cpp)                                     |
 |  1311  |   Medium   | [Get Watched Videos by Your Friends](Problems/1311.cpp)                                          |
+|  1312  |    Hard    | [Minimum Insertion Steps to Make a String Palindrome](Problems/1312.cpp)                         |
 |  1314  |   Medium   | [Matrix Block Sum](Problems/1314.cpp)                                                            |
 |  1315  |   Medium   | [Sum of Nodes with Even-Valued Grandparent](Problems/1315.cpp)                                   |
 |  1319  |   Medium   | [Number of Operations to Make Network Connected](Problems/1319.cpp)                              |