blob: b993e9d3949308ad630dbbfb07441d9595dce62b (
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
// 1312. Minimum Insertion Steps to Make a String Palindrome
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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.
*/
int minInsertions(char *s) {
int n = strlen(s);
int **dp = malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
dp[i] = calloc(n, sizeof(int));
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i + 1])
dp[i][i + 1] = 2;
else
dp[i][i + 1] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j])
dp[i][j] = 2 + dp[i + 1][j - 1];
else
dp[i][j] = fmax(dp[i + 1][j], dp[i][j - 1]);
}
}
int ans = n - dp[0][n - 1];
for (int i = 0; i < n; i++)
free(dp[i]);
free(dp);
return ans;
}
int main() {
char s1[] = {"zzazz"}, s2[] = {"mbadm"}, s3[] = {"leetcode"};
printf("%d\n", minInsertions(s1)); // expect: 0;
printf("%d\n", minInsertions(s2)); // expect: 2;
printf("%d\n", minInsertions(s3)); // expect: 5;
}
|