✅ tips
1.考虑空串,即dp表多出一行一列, 代表某个字符串为空。
2.考虑最后一个位置;是否相等;
3.可在字符串最前面加虚拟位置以对应映射关系;
4.一般横行是j,列是i。此时第一行代表第二个字符串不为空,即第一个字符串是空的
1.最长公共子序列
class Solution {
//dp[i][j]表s1的[0,i]以及s2的[0,j]所有子序列中最长公共子序列的长度;
//如果s[i]=s[j],那公共序列一定是以i,j为结尾
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
s1 = " " + s1;
s2 = " " + s2;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i) == s2.charAt(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[m][n];
}
}
//!=时,有[0,i-1]&[0,j],[0,i-1]&[0,j-1],[0,i]&[0,j-1];空串
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i) == s2.charAt(j)) {
sb.insert(0, s1.charAt(i));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
System.out.println( sb.toString());
2.最长重复子数组
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m=nums1.length;int n=nums2.length;
int[][] dp=new int[m+1][n+1];
int ret=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(nums1[i-1]==nums2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
ret=Math.max(ret,dp[i][j]);
}
}
return ret;
}
}
class Solution {
public int[] findLength(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int maxLength = 0;
int endIndex = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1; // 结束索引
}
}
}
}
int[] result = new int[maxLength];
for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
result[i - (endIndex - maxLength + 1)] = nums1[i];
}
return result;
}
}
class Solution {
public int[] findLength(int[] nums1, int[] nums2) {
int maxLength = 0;
int endIndex = -1;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int len = 0;
while (i + len < nums1.length && j + len < nums2.length && nums1[i + len] == nums2[j + len]) {
len++;
}
if (len > maxLength) {
maxLength = len;
endIndex = i + maxLength - 1;
}
}
}
int[] result = new int[maxLength];
for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
result[i - (endIndex - maxLength + 1)] = nums1[i];
}
return result;
}
}
3.不同的子序列
给你两个字符串
s
和t
,统计并返回在s
的 子序列 中t
出现的个数,结果需要对 109 + 7 取模。示例 1:
输入:s = "rabbbit", t = "rabbit"输出
:3
解释: 如下所示, 有 3 种可以从 s 中得到"rabbit" 的方案
。rabbbit
rabbbit
rabbbit
class Solution {
//dp[i][j]在s的[0,j]的子序列中出现t的[0,i]子串的个数
//是否包含字符s[j]
public int numDistinct(String s, String t) {
int m = t.length(), n = s.length();
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
4.交错字符串
给定三个字符串
s1
、s2
、s3
,请你帮忙验证s3
是否是由s1
和s2
交错 组成的。两个字符串
s
和t
交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ...
或者t1 + s1 + t2 + s2 + t3 + s3 + ...
注意:
a + b
意味着字符串a
和b
连接。示例 1:
输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出:true示例 2:
输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出:false示例 3:
输入:s1 = "", s2 = "", s3 = "" 输出:true提示:
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1
、s2
、和s3
都由小写英文字母组成
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) {
return false;
}
s1 = "" + s1;
s2 = "" + s2;
s3 = "" + s3;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true; // 初始化第一个位置
for (int j = 1; j <= n; j++) { // 初始化第一行
if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= m; i++) { // 初始化第一列
if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
dp[i][0] = true;
} else {
break;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j])
|| (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
}
}
return dp[m][n];
}
}
5.通配符匹配
44. 通配符匹配https://leetcode.cn/problems/wildcard-matching/
给你一个输入字符串 (
s
) 和一个字符模式 (p
) ,请你实现一个支持'?'
和'*'
匹配规则的通配符匹配:
'?'
可以匹配任何单个字符。'*'
可以匹配任意字符序列(包括空字符序列)。判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
输入:s = "aa", p = "a" 输出:false 解释:"a" 无法匹配 "aa" 整个字符串。示例 2:
输入:s = "aa", p = "*" 输出:true 解释:'*' 可以匹配任意字符串。示例 3:
输入:s = "cb", p = "?a" 输出:false 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b
class Solution {
//主要是*可以匹配空符,1个,2个。。。。,s的[0,i],p的[0,j]
public boolean isMatch(String s, String p) {
if (p.equals("*")) return true;
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = true;
}else
break;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];//去一个空符+数学推导
}
}
}
return dp[m][n];
}
}
6.两个字符串的最小ASCII删除和
712. 两个字符串的最小ASCII删除和https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
给定两个字符串
s1
和s2
,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。示例 1:
输入: s1 = "sea", s2 = "eat" 输出: 231 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。 在 "eat" 中删除 "t" 并将 116 加入总和。 结束时,两个字符串相等,115 + 116 = 231 就是符合条件的最小和。示例 2:文章来源:https://www.toymoban.com/news/detail-838249.html
输入: s1 = "delete", s2 = "leet" 输出: 403 解释: 在 "delete" 中删除 "dee" 字符串变成 "let", 将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。 结束时,两个字符串都等于 "let",结果即为 100+101+101+101 = 403 。 如果改为将两个字符串转换为 "lee" 或 "eet",我们会得到 433 或 417 的结果,比答案更大。转化:在两个字符串中找出文章来源地址https://www.toymoban.com/news/detail-838249.html
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int sum = 0;
for (int i = 0; i < m; i++) {
sum += (int) s1.charAt(i);
}
for (int i = 0; i < n; i++) {
sum += (int) s2.charAt(i);
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + (int) s1.charAt(i - 1);
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return sum - 2 * dp[m][n];
}
}
到了这里,关于两个数组的动态规划——最长公共子序列模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!