Open Tcdian opened 4 years ago
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
const dp = Array.from(new Array(word1.length + 1), () => new Array(word2.length + 1));
for (let i = 0; i <= word1.length; i++) {
for (let j = 0; j <= word2.length; j++) {
if (i === 0 || j === 0) {
dp[i][j] = i | j;
} else if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
}
}
}
return dp[word1.length][word2.length];
};
var minDistance = function(word1: string, word2: string): number {
const dp: number[][] = Array.from(new Array(word1.length + 1), () => new Array(word2.length + 1));
for (let i = 0; i <= word1.length; i++) {
for (let j = 0; j <= word2.length; j++) {
if (i === 0 || j === 0) {
dp[i][j] = i | j;
} else if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
}
}
}
return dp[word1.length][word2.length];
};
72. Edit Distance
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符 删除一个字符 替换一个字符
Example 1
Example 2