算法设计------构造回文需插入最少字符数

发表于 | 分类于

问题描述

给定字符串 x = x0…n-1,为构造x为回文最少需要插入几个字符。
例如：

  • x: Ab3bd
  • 可以构造 “dAb3bAd” 或 “Adb3bdA” 通过插入两个字符

问题分析

设Dij表示构造xi…j为回文需插入的最少字符数。

  • 初始情况：
    Dii = Di,i-1 = 0
  • xi = xj
    Dij = Di + 1,j-1
  • xi != xj
    Dij = min{Di+1,j,Di,j-1} + 1

Coding

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
int count_for_dailog(char * x, int i , int j)
{
    if(i == j){
        return 0;
    }
    if(x[i] == x[j]){
        return count_for_dailog(x, i + 1, j - 1);
    }else{
        return 1 + MIN(count_for_dailog(x, i + 1, j), count_for_dailog(x, i, j - 1));
    }
    return 1;
}

时间复杂度

递归实现的时间复杂度为2^n ,最坏情况为，x内所有字符无重复。

动态规划法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int count_for_dailog(char * x , int n){
    int count[n][n];
    //count[i][i]/count[i][i-1] == 0
    for (int i = 1; i < n; i ++) {
        count[i][i] = 0;
        count[i][i - 1] = 0;
    }
    count[0][0] = 0;
    //间隙由大到小
    for (int t = 1; t < n; t ++) {
        for (int i = 0 , j = t; j < n; j ++ , i ++) {
            if (x[i] == x[j]) {
                count[i][j] = count[i + 1][j - 1];
            }else{
                count[i][j] = MIN(count[i + 1][j], count[i][j - 1]) + 1;
            }
        }
    }
    return count[0][n - 1];
}

时间复杂度

递归实现的时间复杂度为n^2。

测试代码

1
2
3
char * x = "Ab3bd";
int count = count_for_dailog(x, 5);
printf("Ab3bd length = %d",count);

Output

1
Ab3bd length = 2

如果对你有帮助的话，Star✨下一吧！