leetcode 72 Solution

代码解析

package com.demo.s72;

/**
 * 编辑距离
 */
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        if(m == 0 || n == 0) {
            return m + n;
        }
        int[][] dp = new int[m + 1][n + 1];
        //j == 0 也就是 words2 长度为0时，编辑距离 完全取决于words1长度
        for(int i = 0; i< m + 1; i++) {
            dp[i][0] = i;
        }
        //i == 0 也就是 words1 长度为0时，编辑距离 完全取决于words2长度
        for(int j = 0; j< n + 1; j++) {
            dp[0][j] = j;
        }

        for(int i = 1; i<= m; i++) {
            for(int j = 1; j<= n; j++) {
                //字符相等 则编辑距离不变
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    //取决于前者编辑距离的最小值 + 1
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}