题解 | #计算字符串的编辑距离#

解题思路：

• 考虑俩种情况
• 一种是：俩个字符串的对应位置相同
• 相同 则不需要变
• 一种是：俩个字符串的对应位置不同
• 不同包含三种类型的操作， 因为dp[i][j] 分表代表的是 i-1的第一个单词和j-1的第二个单词 做对比， 所得到的做小操作次数，
• 所以当对其中某个字符串进行删除操作， 相当于对应减去i或者j 即 dp[i - 1][j] 和dp[i][j - 1]
• 而替换的话， 相当于之前都相同，再增加一次替换操作。

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
        
            String word1 = in.next();
            String word2 = in.next();

            // 以word1 的i-1位置和 word2 的 j-1的位置，相比较 需要的最少编辑次数
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];

            // 初始化
            for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
            for (int j = 0; j <= word2.length(); j++) dp[0][j] = j;

            // 赋值
            for (int i = 1; i <= word1.length(); i++) {
                for (int j = 1; j <= word2.length(); j++) {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        // 和上一个相同 不需要变
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // 需要进行 删除word1 / 删除word2/ 替换 其中一个， 求最小的
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }
                }
            }
            System.out.println(dp[word1.length()][word2.length()]);
        }
    }
}