【牛客刷题20】 计算字符串的编辑距离

文章目录

• 一、题目
• 二、思路

一、题目

题目链接：计算字符串的编辑距离

二、思路

  分析题目：

• 可用的 *** 作：插入、删除、替换
• 一次 *** 作：只能 *** 作一个字符
• 编辑距离：最小的 *** 作数

思路是采用动态规划来做。

问题：字符串A转换成字符串B的编辑距离

子问题：字符串A的一部分转换成字符串B的一部分的编辑距离

状态 F（i,j）：字符串A的前 i 个字符转换成字符串B的前 j 个字符的编辑距离

状态转移方程：F（i,j）：？？？

这个状态转移方程怎么找呢？

A：abcdefg     B：abcdef
F(1,1)： a --> a: 0
F(3,4)：abc -->abcd ：需要插入d
F(3,4): abcd --> abd :这里也可以是删除一个字符d
F(4,4): abcd --> abcd : 0//已经是相同的，不需要做任何 *** 作

假如我们是要求F(i,j）： A[ 1, i ] --> B[ 1, j ]

插入 *** 作：F[ i , j -1 ]: A[ 1, i ] --> B[ 1, j-1] +插入第j个字符。 //把字符A的前i个字符，转变成字符B的前j个字符。
 
删除 *** 作：F[ i -1, j) : A[ 1, i - 1] --> B[ 1, j ] + 删除第i个字符
 
替换 *** 作： A [ i，i-1] --> B[j-1] + A[i] == B[j]。//这里需要判断A[i] 是否等于B[j]，如果相等，则不替换，不相等，则把A的第i个字符替换成B的第j个字符。

问题变成：在上述三种 *** 作之中，选一个最小的。

因此，状态转移方程：

F（i，j）: = min { F(i,j-1) + 1 , F( i - 1 , j - 1) + (A[ i ] == B [ j ] ? 0 : 1) }.

初始状态：F（0，j) = j(插入） F（i,0) = i(删除）

总结：

1. F[ i ] [ j ]=F[ i-1 ] [ j-1 ]，此时已经知道A的前i-1个字符到B的前j-1个字符的距离且A[i]==B[j],不增加距离。

2. F[ i ] [ j ]=F[ i-1 ] [ j-1 ]+1,此时已经知道A的前i-1个字符到B的前j-1个字符的距离且A[i]!=B[j],需要修改A[i]或B[j]，距离+1.

3. F[ i ] [ j ]=F[ i - 1 ] [ j ] + 1,此时已经知道A的前i-1个字符到B的前j个字符的距离，那么A的前i个字符到B的前j个字符就需要加上A的第i个字符，即距离+1

4. F[ i ] [ j ]=F[ i ] [ j-1 ]+1，此时已经知道A的前i个字符到B的前j-1个字符的距离，那么B的前j个字符到A的前i个字符就需要加上B的第j个字符，即距离+1

对应着图看：

代码：

import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()){
            String str1 = scanner.nextLine();
            String str2 = scanner.nextLine();
            System.out.println(getDistance(str1,str2));
        }
    }
    
    public static int getDistance (String str1,String str2){
        char[] wd1 = str1.toCharArray();
        char[] wd2 = str2.toCharArray();
        int len1 = wd1.length;
        int len2 = wd2.length;
        //定义一个矩阵
        int[][] dist = new int[len1 + 1][len2 + 1];
        //初始状态： F（i，0） =i ; F（0，j) == j
        for(int i =1; i<= len1; i++){
            dist[i][0] = i;
        }
        for(int j =0; j<=len2 ;j++){
            dist[0][j] = j;
        }
        for(int i =1; i<= len1; i++){
             for(int j =1; j<= len2;j++){
                 dist[i][j] = Math.min(dist[i-1][j], dist[i][j-1]) +1;
                 if(wd1[i -1] == wd2[j-1]){
                     //如果相等，不需要替换
                     dist[i][j] = Math.min(dist[i][j] , dist[i-1][j-1]);
                 }else{
                     dist[i][j] = Math.min(dist[i][j] , dist[i-1][j-1] +1);
                 }
             }   
        }
        return dist[len1][len2];
    }
}