字符串的修改 （C语言代码）

解题思路

运用动态规划的思想: d[i][j] = 表示第一个字符串str1的前i个字符转换到第二个字符串str2的前j个字符所需要的最小的转换步骤，则当str1[i] == str2[j]时, d[i][j] = d[i-1][j-1]; 当str1[i] != str2[j]时，d[i][j] = min(d[i][j], d[i-1][j-1]+1, d[i-1][j]+1, d[i][j-1]+1);  后三项分别对应修改，删除，添加末尾字符。临界条件为d[i][0] = d[0][i] = i;





注意事项:





参考代码:

#include <stdio.h>

#include <string.h>

#define MAXN 205

#define INF 0x3f3f3f3f;

#define min(a, b) ((a)<(b)?(a):(b))

#define max(a, b) ((a)>(b)?(a):(b))

char str1[MAXN], str2[MAXN];

int d[MAXN][MAXN];

int main()

{

for (int i = 0; i < MAXN; ++i) 

for(int j = 0; j < MAXN; ++j) d[i][j] = INF;

gets(str1+1); gets(str2+1);

int len1 = strlen(str1+1), len2 = strlen(str2+1);

for (int i = 0; i <= max(len1, len2); ++i) d[i][0] = d[0][i] = i;

for (int i = 1; i <= len1; ++i) 

for (int j = 1; j <= len2; ++j)

{

if (str1[i] == str2[j]) { d[i][j] = d[i-1][j-1]; continue; }  // 末尾字符相等

d[i][j] = min(d[i][j], d[i-1][j-1]+1);  // 替换末尾字符

d[i][j] = min(d[i-1][j]+1, d[i][j]);    // 删除末尾字符

d[i][j] = min(d[i][j-1]+1, d[i][j]);    // 末尾添加字符

}

printf("%d\n", d[len1-1][len2-1]);

return 0;

}