leetcode-72-编辑距离

package com.example.demo;

public class Test72 {

    /**
     * 两个字符串的编辑距离
     * e    5   4   4   3
     * s    4   3   3   2
     * r    3   2   2   2
     * o    2   2   1   2
     * h    1   1   2   3
     * ‘‘   0   1   2   3
     * i/j  ‘‘  r   o   s
     * 状态转移方程：
     * 当word1的第i个字符等于，word2的第j个字符，则
     * dp[i][j] = dp[i-1][j-1]
     * 当不等于时
     * dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     */
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1 == 0 || len2 == 0) {
            return len1 + len2;
        }

        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化 当空串word1，转换为串word2需要的步数 ，即dp[0][j]
        // 初试话 当串word1，转换为空串word2需要的部署，即dp[i][0]
        for (int i = 0; i < len1 + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < len2 + 1; i++) {
            dp[0][i] = i;
        }
        // 动态规划状态转移方程
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }

        return dp[len1][len2];
    }


    public static void main(String[] args) {
        Test72 t = new Test72();
        int i = t.minDistance("horse", "ros");
        System.out.println(i);
    }
}