动态规划8: 单词最小编辑距离

给定两个单词，word1, word2, 可以对单词进行insert, delete, replace操作，但每次只能操作一个字符，问最少经过多少步可以将word1修改为word2.

如 word1: horse, word2: rose.

需要对word1进行的操作过程如下：

• replace h 为 r
• delete r

最少2步。

分析

对于单词编辑距离的状态定义，是有个套路的：

定义状态DP[i][j]为word1前i个字符串编辑为word2前j个字符串所需的最少步数。最终DP[word1.length][word2.length]为所求。

状态转移方程为：

DP[i][j] =
word1[i] === word2[j] ?
DP[i-1][j-1]:
min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1])+1

状态转移关系解读：
如果word1[i]与word2[j]的字符相同： 则DP[i][j]等于DP[i-1][j-1]，不用多操作一步；
在不等的情况下：

• word1前i个字符转换为了word2前j-1个字符的情况下， word1需要操作insert.
• word1前i-1个字符转换为了word2前j个字符的情况下，word1需要操作delete
• word1前i-1个字符转换为了word2前j-1个字符的情况下, word1需要操作replace.

初始值：

i===0时，DP[i][j] = j; // 此前word1前0个字符为空，需要insert j次
j===0时，DP[i][j] = i; // 需要delete i次

function editDistance(word1, word2) {
    word1 = ' ' + word1;// 添加一个空字符串，容易赋初值
    word2 = ' ' + word2;
    const len1 = word1.length;
    const len2 = word2.length;

    // 初始化二维数组
    const DP = new Array(len1);
    for(i=0; i< len1; i++) {
        DP[i] = [];
    }

    // 初始值
    for(let i=0; i< len1; i++) {
        DP[i][0] = i;
    }
    for(let j=0; j< len2; j++) {
        DP[0][j] = j;
    }
    DP[0][0] = 0;

    for(let i = 1; i < len1; i++) {
        for(let j = 1; j < len2; j++) {
            if(word1[i] === word2[j]){
                DP[i][j] = DP[i-1][j-1];
            } else {
                DP[i][j] = Math.min(DP[i-1][j-1], DP[i][j-1], DP[i-1][j]) + 1;
            }
        }
    }

    return DP[len1-1][len2-1];
}