aboutsummaryrefslogtreecommitdiff
path: root/min_insertion_make_palindrome.cpp
blob: 7af74da3641d4e9a04d6e9fcc02d3f6b260a3abe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
}