代码随想录算法训练营第三十九天

其他:

今日总结
往期打卡

---

115. 不同的子序列

跳转: 115. 不同的子序列

学习: 代码随想录公开讲解

问题:

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

测试用例保证结果在 32 位有符号整数范围内。

思路:

单字符串删减求子序列数

考虑s元素选与不选,或删除s中的元素,看是否和t相等
dp数组值的含义是s长为i,t长为i时子序列的个数.
对于 i,如果选了就计数分裂成两部分(两个都没选,和s少选一个的情况),如果没选就要继承上次的选择当跳过这次选择
需要基于遍历过的(s少选一个)递推,所以需要顺序遍历
初始化将所有t为0初始化为1,t为0时一定有一个,而t不为0s为0需要初始化为0,其余部分皆可会覆盖,所以除了1统一默认即可.

复杂度:

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(nm)$

代码:

class Solution {public int numDistinct(String s, String t) {int n = s.length();int m = t.length();int[][] dp = new int[n+1][m+1];for(int i=0;i<=n;i++){dp[i][0] = 1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];else dp[i][j] = dp[i-1][j];}}return dp[n][m];}
}

---

583. 两个字符串的删除操作

跳转: 583. 两个字符串的删除操作

学习: 代码随想录公开讲解

问题:

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

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

思路:

两字符串可删除求最小相等步数
按最小步数初始化分别为0的情况(另一个全部删除)
递推公式就是相等就和上一次一样,不然就考虑都删,删一个里最小的情况
基于更新过的状态,顺序遍历

复杂度:

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(nm)$

代码:

class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();int[][] dp = new int[n+1][m+1];for(int i=1;i<=n;i++){dp[i][0] = i;}for(int i=1;i<=m;i++){dp[0][i] = i;}for(int i=1;i<=n;i++){for(int j=1;j<=m;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-1]+2,Math.min(dp[i-1][j],dp[i][j-1])+1);}}// for(var arr:dp)// System.out.println(Arrays.toString(arr));return dp[n][m];}
}

---

72. 编辑距离

跳转: 72. 编辑距离

学习: 代码随想录公开讲解

问题:

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

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

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

思路:

一个字符串增删改,求最小操作
增一个可以看作另一个删,改就是可以一步从都删跳到当前
上一题稍微改一下即可.

复杂度:

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(nm)$

代码:

class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();int[][] dp = new int[n+1][m+1];for(int i=1;i<=n;i++){dp[i][0] = i;}for(int i=1;i<=m;i++){dp[0][i] = i;}for(int i=1;i<=n;i++){for(int j=1;j<=m;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-1]+1,Math.min(dp[i-1][j],dp[i][j-1])+1);}}return dp[n][m];}
}

---

总结

练习了编辑距离问题,核心在于i,j两个下标分别表示两个字符串遍历到i,j
可以通过赋值为之前的下标表示删除或修改,增加操作可以逆向看作删除令一个

往期打卡

代码随想录算法训练营第三十八天

代码随想录算法训练营第三十七天

代码随想录算法训练营第三十五&三十六天

代码随想录算法训练营第三十四天

代码随想录算法训练营第三十三天(补)

代码随想录算法训练营第三十二天

代码随想录算法训练营第三十一天

代码随想录算法训练营第三十天(补)

代码随想录算法训练营第二十九天

代码随想录算法训练营第二十八天

代码随想录算法训练营第二十七天(补)

代码随想录算法训练营第二十六天

代码随想录算法训练营第二十五天

代码随想录算法训练营第二十四天

代码随想录算法训练营第二十三天

代码随想录算法训练营周末四

代码随想录算法训练营第二十二天(补)

代码随想录算法训练营第二十一天

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天