给定两个单词，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];
}
