题目描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

Ex：
字符串A:abcdefg
字符串B: abcdef
通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。

题解

• 构建一个dp数组
  这里数组长度要在原始字符串长度加1 若长度为4字符串和长度为6字符串比较则需构建一个5行7列的dp数组
• 边界条件
  当i=0 或 j=0时 字符串的距离就是改字符所在位置，即 j 或 i的值
• 状态转移方程
  那么如果s1[i]==s2[j]，显然不需要进行操作，dp[i][j]==dp[i-1][j-1]；
  如果s1[i]!=s2[j]，dp[i][j]就是取dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]最小值加1

		d	i	s	t	i	n
	0	1	2	3	4	5	6
d	1	0	1	2	3	4	5
i	2	1	0	2	3	4	5
v	3	2	1	1	2	3	4
e	4	3	2	2	2	3	4

最后结果就是dp[i+1][j+1]

动态规划

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            String str1 = str;
            String str2 = br.readLine();
            
            System.out.println(mm(str1, str2));
        }
    }

    public static int mm(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        int min = 0;
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i==0 || j==0){
                    dp[i][j] = Math.max(i,j);
                }else{
                    min = Math.min( dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1]));
                    if (str1.charAt(i-1) == str2.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        dp[i][j] = min + 1;
                    }
                }
            }
        }
        return dp[len1][len2];
    }
}