aboutsummaryrefslogtreecommitdiff
path: root/other/min_insertion_make_palindrome.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_insertion_make_palindrome.cpp')
-rw-r--r--other/min_insertion_make_palindrome.cpp32
1 files changed, 32 insertions, 0 deletions
diff --git a/other/min_insertion_make_palindrome.cpp b/other/min_insertion_make_palindrome.cpp
new file mode 100644
index 0000000..7af74da
--- /dev/null
+++ b/other/min_insertion_make_palindrome.cpp
@@ -0,0 +1,32 @@
+// 1312. Minimum Insertion Steps to Make a String Palindrome
+#include "leetcode.h"
+
+/*
+ * given string 's'. in one step you can insert any character at any index of
+ * the string. return the minimum number of steps to make 's' palindrome. a
+ * palindrome string is one that reads the same backward as well as forward.
+ */
+
+class Solution {
+public:
+ int minInsertions(string s) {
+ vector<int> memo(s.size(), 0);
+ int prv, tmp;
+ for (int i = s.size() - 2; i >= 0; i--) {
+ prv = 0;
+ for (int j = i; j < s.size(); j++) {
+ tmp = memo[j];
+ memo[j] = s[i] == s[j] ? prv : 1 + min(memo[j], memo[j - 1]);
+ prv = tmp;
+ }
+ }
+ return memo[s.size() - 1];
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.minInsertions("zzazz")); // expect: 0
+ printf("%d\n", obj.minInsertions("mbadm")); // expect: 2
+ printf("%d\n", obj.minInsertions("leetcode")); // expect: 5
+}