73 lines
2.1 KiB
JavaScript
73 lines
2.1 KiB
JavaScript
/**
|
||
* @param {string} word1
|
||
* @param {string} word2
|
||
* @return {number}
|
||
*/
|
||
const minDistance = function (word1, word2) {
|
||
|
||
};
|
||
|
||
/*
|
||
这个题看似无从下手，其实反过来思考非常容易，直接求出最长的公共子序列，然后步数就是这个两个字符串中多出的那几个字符的和
|
||
*/
|
||
|
||
function f1(word1, word2) {
|
||
const commonLen = longestCommonSubsequence(word1, word2);
|
||
return word1.length + word2.length - 2 * commonLen;
|
||
}
|
||
|
||
function longestCommonSubsequence(text1, text2) {
|
||
const m = text1.length;
|
||
const n = text2.length;
|
||
|
||
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
|
||
|
||
for (let i = m - 1; i >= 0; i--) {
|
||
for (let j = n - 1; j >= 0; j--) {
|
||
if (text1[i] === text2[j]) {
|
||
dp[i][j] = dp[i + 1][j + 1] + 1;
|
||
} else {
|
||
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
|
||
}
|
||
}
|
||
}
|
||
return dp[0][0];
|
||
}
|
||
|
||
/*
|
||
直接利用动态规划，来求解，定义dp[i][j]为s1中前i个字符和s2中前j个字符，变得相同需要删除的字符数量的最少个数，第i个字符是s1[i-1]
|
||
同理第j个字符是s2[j-1]注意这里的dp[i][j]的定义是前i个字符，从1开始数的，之所以要这样定义，是因为s1可以为空字符，需要使用dp[0][0]
|
||
来表示空字符
|
||
*/
|
||
|
||
function f2(word1, word2) {
|
||
const m = word1.length;
|
||
const n = word2.length;
|
||
|
||
// 定义dp表m+1行，n+1列
|
||
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // 初始化成0没有特殊意义，反正都要填表
|
||
|
||
// 初始第一行，s1为空字符串，那么当s2有多少个字符就取出多少个，即dp[0][j] = j
|
||
for (let j = 0; j <= n; j++) {
|
||
dp[0][j] = j;
|
||
}
|
||
|
||
// 列同理
|
||
for (let i = 0; i <= m; i++) {
|
||
dp[i][0] = i;
|
||
}
|
||
|
||
// 填充dp表从上到下，从左到右
|
||
for (let i = 1; i <= m; i++) {
|
||
for (let j = 1; j <= n; j++) {
|
||
if (word1[i - 1] === word2[j - 1]) { // 如果第i个字符和第j个字符相等
|
||
dp[i][j] = dp[i - 1][j - 1];
|
||
} else {
|
||
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
|
||
}
|
||
}
|
||
}
|
||
|
||
return dp[m][n];
|
||
}
|