#yyds幹貨盤點# 動态規劃專題：計算字元串的編輯距離

1.簡述：

描述

Levenshtein 距離，又稱編輯距離，指的是兩個字元串之間，由一個轉換成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。編輯距離的算法是首先由俄國科學家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

例如：

字元串A: abcdefg

字元串B: abcdef

通過增加或是删掉字元 ”g” 的方式達到目的。這兩種方案都需要一次操作。把這個操作所需要的次數定義為兩個字元串的距離。

要求：

給定任意兩個字元串，寫出一個算法計算它們的編輯距離。

資料範圍：給定的字元串長度滿足 

輸入描述：

每組用例一共2行，為輸入的兩個字元串

輸出描述：

每組用例輸出一行，代表字元串的距離

示例1

輸入：

abcdefg
abcdef      

1      

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s1 = sc.next();
            String s2 = sc.next();
            int dp[][] = new int[s1.length()+1][s2.length()+1];
            dp[0][0] = 0;
            for(int i = 1;i<dp.length;i++){
                dp[i][0] = i;
            }
            for(int i = 1;i<dp[0].length;i++){
                dp[0][i] = i;
            }
            for(int i = 1;i<dp.length;i++){
                for(int j = 1;j<dp[0].length;j++){
                    if(s1.charAt(i-1)==s2.charAt(j-1))
                    {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    else {
                        dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
                    }
                }
            }
            System.out.println(dp[s1.length()][s2.length()]);
        }
    }
}