文章目录
系列文章目录前言题录392. 判断子序列115. 不同的子序列583. 两个字符串的删除操作72. 编辑距离系列文章目录
一、 数组类型解题方法一：二分法
二、数组类型解题方法二：双指针法
三、数组类型解题方法三：滑动窗口
四、数组类型解题方法四：模拟
五、链表篇之链表的基础操作和经典题目
六、哈希表篇之经典题目
七、字符串篇之经典题目
八、字符串篇之 KMP
九、解题方法：双指针
十、栈与队列篇之经典题目
十 一、栈与队列篇之 top-K 问题
十 二、二叉树篇之二叉树的前中后序遍历
十 三、二叉树篇之二叉树的层序遍历及相关题目
十 四、二叉树篇之二叉树的属性相关题目
十 五、 二叉树篇之二叉树的修改与构造
十 六、 二叉树篇之二叉搜索树的属性
十 七、二叉树篇之公共祖先问题
十 八、二叉树篇之二叉搜索树的修改与构造
十 九、回溯算法篇之组合问题
二 十、回溯算法篇之分割、子集、全排列问题
二十一、贪心算法篇之入门题目
二十二、贪心算法篇之进阶题目
二十三、动态规划篇之基础题目
二十四、动态规划篇之背包问题：01背包
二十五、动态规划篇之背包问题：完全背包
二十六、动态规划篇之经典问题：打家劫舍
二十七、动态规划篇之买股票问题（一）
二十八、动态规划篇之子序列问题：连续子序列和不连续子序列
更新中 ……
前言
前三道题是理解困难题目编辑距离的基础。
刷题路线来自 ：代码随想录
题录
392. 判断子序列
Leetcode 链接
题解：
还是求公共子序列，只不过这里 s 连续，t 不连续，可以像上篇一样 dp数组 记录公共子序列长度，最后判断一下长度是否等于 s 长度，也可以直接使用一个 boolean 类型的 dp 数组，这里使用后者。
状态 dp[i][j]：表示以 i - 1 结尾的 s 子串是不是 t 的[0, j] 区间的子串 的子序列
递推公式：
如果 s.charAt(i - 1) == t.charAt(j - 1)，dp[i][j] = dp[i - 1][j - 1]
否则 dp[i][j] = dp[i][j - 1]; 因为要找 s 是不是 t 的子串，某个状态的 s 为 [0, i - 1] 的子串，且不能更改，所以只能缩短 t 串的区间，根据本层前边的状态得出当前状态的值。
初始化：第一行初始化为 true。
class Solution {public boolean isSubsequence(String s, String t) {int row = s.length();int col = t.length();boolean[][] dp = new boolean[row + 1][col + 1];// 初始化for (int i = 0; i <= col; i++) {dp[0][i] = true;}for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[row][col];}}
双指针更快哈哈哈
class Solution {public boolean isSubsequence(String s, String t) {int i = 0;int j = 0;while (i < s.length() && j < t.length()) {if (s.charAt(i) == t.charAt(j)) {i++; } j++;}return i == s.length();}}
115. 不同的子序列
Leetcode 链接
题解：
换个说法，计算 t 在 s 的不连续子串中出现的次数。
t 作为 row，s 作为 col，寻找 t 在 s 中有多少种组合
状态 dp[i][j]：表示 t 下标从0 到 i - 1的子串在 [0, j - 1] 区间 s 的所有子串中有多少种组合方式。
不相等是，t 作为连续串，所以只能根据该层 dp 数组前边的状态得到当前状态的值
手画一遍图就明白递推公式的意思了。
class Solution {public int numDistinct(String s, String t) {int row = t.length();int col = s.length();int[][] dp = new int[row + 1][col + 1];for (int i = 0; i <= col; i++) {dp[0][i] = 1;}for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (t.charAt(i - 1) == s.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[row][col];}}
583. 两个字符串的删除操作
Leetcode 链接
题解：
方式一：同上篇提到的 1143. 最长公共子序列，计算出最长公共子序列长度，然后用总分长度减去公共长度就是需要删除的长度
class Solution {public int minDistance(String word1, String word2) {int row = word1.length();int col = word2.length();int[][] dp = new int[row + 1][col + 1];for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return row + col - 2 * dp[row][col];}}
方式二：
dp[i][j] 就表示 [0, i - 1] 的 word1 和 [0, j - 1] 的 word2 需要删除的最少长度
递推公式：每次比较 word1.charAt(i - 1) 和 word2.charAt(j - 1)
如果相等：dp[i][j] 取 dp[i - 1][j - 1]，因为不用删除
如果不相等：dp[i][j] 取 dp[i - 1][j] 和 dp[i][j - 1] 中最小的值加一；用一个例子解释：
如 “sea” 和 “eat” 中 i = j = 3 时，a 和 t 不同，去 “aea” 和 “ea” 、“se” 和 “eat” 这两个状态取最小的一种状态 加上 1（1 表示新增的字符，不相等应该删除）。
class Solution {public int minDistance(String word1, String word2) {int row = word1.length();int col = word2.length();int[][] dp = new int[row + 1][col + 1];for (int i = 0; i <= row; i++) {dp[i][0] = i;}for (int i = 1; i <= col; i++) {dp[0][i] = i;}for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (word1.charAt(i - 1) == word2.charAt(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[row][col];}}
72. 编辑距离
Leetcode 链接
题解：
if (word1[i - 1] == word2[j - 1])不操作if (word1[i - 1] != word2[j - 1])增删换
增和删操作次数是一样的，如 ros 和 rs，给 rs 中间增添一个 o，或者删除 ros 中间的 o。
状态 dp[i][j]：表示以下标 i-1 为结尾的字符串 word1，和以下标 j-1 为结尾的字符串 word2 的编辑距离
递推公式：
不操作：[i][j] = dp[i - 1][j - 1]
操作：
替换：dp[i][j] = dp[i - 1][j - 1] + 1，新增的两个字符其中一个替换为另一个
增删：dp[i][j - 1] + 1、dp[i- 1][j] + 1，word1 和 word2 一个不动，操作另一个
取三者中操作次数最小的
class Solution {public int minDistance(String word1, String word2) {int row = word1.length();int col = word2.length();int dp[][] = new int[row + 1][col + 1];for (int i = 0; i <= row; i++) {dp[i][0] = i;}for (int i = 0; i <= col; i++) {dp[0][i] = i;}for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;}}}return dp[row][col];}}
如果觉得《Leetcode 刷题笔记(二十九) ——动态规划篇之子序列问题：编辑距离》对你有帮助，请点赞、收藏，并留下你的观点哦！
