题解 | #编辑距离#

import java.util.*;


/** 编辑距离
 * 给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
 * 你可以对一个单词执行以下3种操作：
 * a）在单词中插入一个字符
 * b）删除单词中的一个字符
 * c）替换单词中的一个字符
 * 状态: 将word1的前i个字符变为word2的前j个字符需要多少步 f(i, j)
 * 分析: 三种操作 i: 插入操作: f(i, j-1) ->f(i, j)
 *              d: 删除操作: f(i-1, j)+1 ->f(i, j)
 *              r: 替换操作: 1. word1[i] != word2[j]时: f(i-1, j-1) -> f(i, j)
 *       三种操作中取最小值
 * 转移方程: f(i, j) = min( f(i-1, j), f(i+1, j))
 *         if(word1[i]!=word[j]) f(i-1,j-1)+1
 *         else f(i-1, j-1)+1 -> f(i, j)
 * 初始状态: f[0][i] = i
 *         f[i][0] = i
 */
public class Solution {
    public int minDistance (String word1, String word2) {
        // write code here
        if(word1.isEmpty() || word2.isEmpty()){
            return Math.max(word1.length(), word2.length());
        }
        int row = word1.length();
        int col = word2.length();
        int [][]mind = new int[row+1][col+1];
        //初始化
        for(int i=0;i<=row;i++){
            mind[i][0]=i;
        }
        for(int i=0;i<=col;i++){
            mind[0][i]=i;
        }
        for(int i=1; i<=row;i++){
            for(int j=1; j<=col ;j++){
                mind[i][j] = Math.min(mind[i][j-1], mind[i-1][j])+1;
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    mind[i][j] = Math.min(mind[i][j], mind[i-1][j-1]);
                } else {
                    mind[i][j] = Math.min(mind[i][j], mind[i-1][j-1]+1);
                }
            }
        }
        return mind[row][col];
    }
}