编辑距离系列

• 392.判断子序列
• 115.不同的子序列
• 583.两个字符串的删除操作
• 72.编辑距离

解题思路

和买卖股票差不多，先分为最末尾字符是否相同，再分相同和不相同的时候两个字符串之间的操作有什么

判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

代码实现

const dp = new Array(s.length + 1).fill(0).map(() => new Array(t.length + 1).fill(0));
for (let i = 1; i <= s.length; i++) {
  for (let j = 1; j <= t.length; j++) {
    if (s[i - 1] === t[j - 1]) {
      //t中找到了一个字符在s中也出现了
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      //相当于t要删除元素，继续匹配
      dp[i][j] = dp[i][j - 1];
    }
  }
}
return dp[s.length][t.length] === s.length;

不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数

代码实现

const dp: number[][] = Array.from({ length: t.length + 1 }, () => Array.from({ length: s.length + 1 }, () => 0));
for (let i = 0; i <= s.length; i++) {
  dp[0][i] = 1;
}
for (let i = 1; i <= t.length; i++) {
  for (let j = 1; j <= s.length; j++) {
    if (t[i - 1] === s[j - 1]) {
      // 如果当前字符相等，那么当前字符可以选择也可以不选择
      dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
    } else {
      // 如果当前字符不相等，那么当前字符只能不选择
      dp[i][j] = dp[i][j - 1];
    }
  }
}
return dp[t.length][s.length];

两个字符串的删除操作

给定两个单词word1和word2，返回使得word1和 word2相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

代码实现

const dp: number[][] = new Array(word1.length + 1).fill(0).map(() => new Array(word2.length + 1).fill(0));
for (let i = 0; i <= word1.length; i++) {
  dp[i][0] = i;
}
for (let i = 0; i <= word2.length; i++) {
  dp[0][i] = i;
}
for (let i = 1; i <= word1.length; i++) {
  for (let j = 1; j <= word2.length; j++) {
    if (word1[i - 1] === word2[j - 1]) {
      // 如果当前字符相等，那么当前字符不必被删除
      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[word1.length][word2.length];

编辑距离

给你两个单词word1和word2， 请返回将word1转换成word2所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

代码实现

//dp[i][j] 表示以下标i-1为结尾的字符串word1，
//和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
const dp: number[][] = new Array(word1.length + 1).fill(0).map(() => new Array(word2.length + 1).fill(0));
for (let i = 0; i <= word1.length; i++) {
  dp[i][0] = i;
}
for (let i = 0; i <= word2.length; i++) {
  dp[0][i] = i;
}
for (let i = 1; i <= word1.length; i++) {
  for (let j = 1; j <= word2.length; j++) {
    if (word1[i - 1] === word2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1];
    } else {
      //如果结尾字符不相同，要么删除（添加等于删除另一个）一个或者替换一个
      dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
    }
  }
}
return dp[word1.length][word2.length];