Chybeta

hihoCoder 162周:回文字符串

回文字符串。动态规划。

题目

描述

给定一个字符串 S ,最少需要几次增删改操作可以把 S 变成一个回文字符串?一次操作可以在任意位置插入一个字符,或者删除任意一个字符,或者把任意一个字符修改成任意其他字符。

输入

字符串 S。S 的长度不超过100, 只包含’A’-‘Z’。

输出

最少的修改次数。

样例输入

ABAD

样例输出

1

分析

这题采用动态规划。

读入的字符串假设用s表示。则s[i..j],表示从下标为i的字符到下标为j的字符所组成的字符子串(字符串下标从0开始),而s[i]表示下标为i的字符。例如,字符串“ABCD”,则s[0,2]表示字符串“ABC”,s[1]为字符“B”。

用一个二维数组dp[i][j]来保存状态,其中对于每个dp[i][j],表示对字符串s[i..j],使之成为回文字符串所需的最少操作。

现在考察子串s[i..j]。

第一种情况,首尾恰好相同,即 s[i] == s[j]。则对于子串s[i..j]而言,它要变成回文字符串所需的最少操作,与子串s[i-1..j-1]变成回文字符串所需的最少操作数相同。所以有 dp[i][j] = dp[i-1][j+1]

第二种情况,首尾不同,即 s[i] != s[j]。要想让子串s[i..j]变成回文字符串,我们可以利用题目提供的三种操作:增加,删除,修改。

接下来我们分情况讨论。

  1. 假设 s[i..j-1] 是回文字符串。则我们可以在s[i]之前添加上一个字符,使之匹配字符s[j],从而让 s[i..j] 成为回文字符串。此时,dp[i][j] = dp[i][j-1] + 1。或者,我们直接删除掉字符s[j],让 s[i..j] 变成s[i..j-1],从而成为回文字符串,此时同样,dp[i][j] = dp[i][j-1] + 1

  2. 假设 s[i+1..j] 是回文字符串。则我们可以在s[j]之后添加一个字符,使之匹配字符s[i],从而让 s[i..j] 成为回文字符串,此时,dp[i][j] = dp[i+1][j] + 1。或者,我们直接将字符s[i]删掉,让 s[i..j] 变成 s[i+1,j],从而成为回文字符串,此时也有 dp[i][j] = dp[i+1][j] + 1。

  3. 假设 s[i-1..j-1] 是回文字符串。则我们可以修改s[i],使之匹配s[j],或者修改s[j],使之匹配s[i]。这种情况下,有:d[i][j] = dp[i-1][j-1] + 1

以上三种情况,囊括了对字符串s[i..j]所能操作的所有情况。而为求最小操作数,只要取三种情况的最小值。

代码

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define MAX_N 1005
using namespace std;
char str[MAX_N];
int dp[MAX_N][MAX_N];
int min_dp(int a,int b,int c){
int temp = a>b?b:a;
return temp>c?c:temp;
}
int main()
{
scanf("%s",str);
int len = strlen(str);
memset(dp, 0, sizeof(dp));
for (int i=len-1 ;i>=0 ;i--){
for (int j=i ;j<len ;j++){
if ( str[i] == str[j]){
dp[i][j] = dp[i+1][j-1];
}else{
dp[i][j] = min_dp(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]) + 1;
}
}
}
}
printf("%d",dp[0][len-1]);
return 0;
}
点击赞赏二维码,您的支持将鼓励我继续创作!
chybeta WeChat Pay

微信打赏

chybeta Alipay

支付宝打赏