题目描述

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T？

输入格式

输入两行，每行一个字符串。

第一行的字符串为 S，第二行的字符串为 T。

两个字符串均非空而且只包含大写英文字母。

输出格式

输出一个整数，表示答案。

数据范围
1≤|T|≤|S|≤1000

输入样例：

ABCDEABCD
XAABZ

输出样例：

3

算法

编辑距离（dp）

参考文献

https://zhuanlan.zhihu.com/p/80682302 知乎 labuladong的算法专栏

java代码

import java.io.*;
public class Main {
    static int Inf=100000;//此处用一个较大的整数表示无穷
    static int N=1010;
    public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s1=br.readLine();//S
String s2=br.readLine();//T
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[N][N];
    /*dp这个二维数组中，竖列代表s1,横列代表s2,s2比s1短，到后面会有很多空串，
    无论怎么修改都不会使空串变长，故先全部初始化为无穷；
    与之区别。s1先全部初始化为0
    注意代码 先后顺序 ，要保证dp[0][0]=0
    */
        for(int j=0;j<=n;j++)
            dp[0][j] = Inf;
        for (int i = 0; i <= m; i++)
            dp[i][0] = 0;  
    //查改过程 
        for (int i = 1; i <=m; i++){
            for (int j = 1; j <=n; j++){
                dp[i][j] =dp[i - 1][j];//如果s1的前i个包括s2的前j个，那么s1的前i-1个应该也包括s2的前j个
                if (s1.charAt(i-1) == s2.charAt(j-1))
                //这里和其它答案写得不太一样，但是不减一的话会导致下标超出范围值
                    dp[i][j] = min(dp[i - 1][j - 1],dp[i][j]);//相当于不作处理直接跳过
                else
                    dp[i][j] = min(dp[i - 1][j - 1]+1,dp[i][j]);//操作数加一
        // 储存着整个 s1 和 s2 的最小编辑距离
        }}
        System.out.println(dp[m][n]);
    }
    private static int min(int a, int b) {
        return Math.min(a, b);
    }
}

关于算法思想本身

伪代码：

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    // base case 
    for (int i = 1; i <= m; i++)
        dp[i][0] = i;
    for (int j = 1; j <= n; j++)
        dp[0][j] = j;
    // 自底向上求解
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (s1.charAt(i-1) == s2.charAt(j-1))
                dp[i][j] = dp[i - 1][j - 1];
            else               
                dp[i][j] = min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i-1][j-1] + 1
                );
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

其中

//是对s1进行操作
dp(i-1, j ) + 1  //i前移，说明 删 掉了s1的第i个字符
dp(i, j - 1) + 1  //j前移，说明在s1的i处 插入 了s2对应的字符，使得其能够匹配上，所以跳到前一个
dp(i-1, j - 1) + 1 // i,j都前移，说明是 替换
//三者都是使操作数加一