字符串的修改1205

解题思路:公式或者动态规划

注意事项:

参考代码:

一、套公式：最少操作数=长字符串长度-最大公共子串长度

#include

二、动态规划——WagnerFischer算法

#include <stdio.h>
#include <string.h>
int myMin(int a, int b) {
    return a < b ? a : b;
}
int main()
{
    int dp[200][200];//矩阵序列
    char a[200],b[200];//存储字符串
    int na,nb;
   
    gets(a);
    na=strlen(a);
    gets(b);
    nb=strlen(b);
   
    // dp[i][j]表示s1[0]-s1[i]子串变成s2[0]-s2[j]一样所需要的字符操作次数
   
    for (int i = 0; i <=nb; i++)
        dp[0][i] = i;
    for (int i = 0; i <=na; i++)
        dp[i][0] = i;
   
    for (int i = 1; i <= na; i++) {
        for (int j = 1; j <= nb; j++) {
            // 若s1[i]==s2[j]，则dp[i][j]==dp[i-1][j-1]，表示不需要操作
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
            // 若s1[i]!=s2[j]，则可能的操作有替换、插入、删除三种方法，分别由前一步得出，并取最小值。
                dp[i][j] = myMin(myMin(dp[i - 1][j], dp[i - 1][j - 1]), dp[i][j - 1] )+1;
        }
    }
     /*  
    for (int i = 0; i <= na; i++) {
        for (int j = 0; j <= nb; j++) {
            printf("%d ",dp[i][j]);
        }
        printf("\n");
    }
    */
    printf("%d",dp[na][nb]);
    return 0;
}