1. 最长公共子序列
1143. 最长公共子序列
状态表示:
dp[i][j] 表示 s1 的 0 ~ i 区间和 s2 的 0 ~ j 区间内所有子序列中,最长公共子序列的长度
状态转移方程:
当 s1[i] 和 s2[j] 相等时,那么最长公共子序列一定是以这两个位置为结尾的,所以就可以直接取 i - 1 ~ j - 1 区间内再去找,dp[i - 1][j - 1] 的结果加上确定好的 1 即可,如果不相等的话,就可以去 s1 的 i - 1 位置和 s2 的 j 继续找,或者是从 s1 的 i 位置和 s2 的 j - 1位置找,i - 1, j - 1 的情况已经被包含在这两种情况中了,所以可以不考虑这种情况,上面的情况找出最大值就是不相等时的 dp[i][j]
初始化:为了防止不越界,可以把数组多开一行和一列,初始化为 0 即可
填表顺序:从左到右,从上到下
返回值:dp[m][n]
class Solution {
public int longestCommonSubsequence(String t1, String t2) {
int m = t1.length(),n = t2.length();
char[] s1 = t1.toCharArray();
char[] s2 = t2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(s1[i - 1] == s2[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 dp[m][n];
}
}
2. 不相交的线
1035. 不相交的线
和上一题一样
3. 不同的子序列
115. 不同的子序列
状态表示:
dp[i][j] :s 字符串[0 , j] 区间内所有的子序列中,有多少个 t 字符 [0 , i] 区间内的子串
当 t[i] ≠ s[j] 时,就要从 j - 1 位置开始找,因为需要找到子串 t 区间是连续的,所以 i 位置不能动,也就是 dp[i][j] = dp[i][j - 1],如果 t[i] = s[j] 时,那么就还需要加上 dp[i - 1][j - 1]
初始化:为了防止越界,需要多开一行和一列,那么 i = 0 时,也就是 t 是空串的话,s 中枚举到哪个位置都是会包含一种方案的,也就是 i = 0 时都需要初始化为 1
填表顺序:从左到右,从上到下
返回值:dp[n][m]
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[n + 1][m + 1];
for(int i = 0;i < m + 1;i++){
dp[0][i] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;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[n][m];
}
}
4. 通配符匹配
44. 通配符匹配
状态表示:
dp[i][j] 表示字符串 p [0 , j ] 区间内是否能匹配字符串 s 区间 [0 , i ] 区间内的子串
状态转移方程:
字符串 p 的 j 位置可以分为普通字符,? ,* 三种情况,当是普通字符时,就需要判断 s[i] 和 p[j] 是否相等,如果相等,并且 dp[i - 1][j - 1] 也是 true ,那么 dp[i][j] 就是 true,如果是 ? 的话,直接就等于 dp[i][j],如果是 * 的话,由于 * 可以匹配任意个字符,所以可以由之前的任意状态表示,但是这么多状态如果用循环来表示的话就可能超时,这种情况是可以优化一下的
可以通过数学变换来得出 dp[i][j] 是等于 dp[i][j] || dp[i - 1][j] 的
还可以用另一种思路:
' * ' 可以匹配空串,此时就要往 dp[i][j - 1] 中找答案,也可以匹配一个字符,但是不舍去,下一次还可以用来匹配一个字符或者空串,这样就达到了匹配多个字符的效果
初始化:可以通过引入空串的方式来初始化,防止填表时越界
(0 , 0 ) 位置肯定就是 true ,因为引入空串之后两个字符的 0 下标都是空字符串,可以匹配,但是当 j++ 时,也就是字符串 p 之后是 * 的话才能匹配空串,只要遇到不是 * ,后面都是 false,而第一列 1 下标之后,表示 p 的空串去匹配字符串 s ,肯定都是 false
填表顺序:从左到右
返回值:dp[m][n]
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(),n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
s = " " + s;
p = " " + p;
dp[0][0] = true;
int index = 1;
while(index <= n){
if(p.charAt(index) == '*'){
dp[0][index] = true;
index++;
}else{
break;
}
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(p.charAt(j) == '*'){
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}else{
if(p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
5. 正则表达式匹配
10. 正则表达式匹配
状态表示:
dp[i][j] 表示字符串 p[0 , j] 区间内的子串能否匹配字符串 s [0 , i ] 区间内的子串
状态转移方程:
根据最后一个字符的状态可以分为下面这几种情况
当字符串 p 最后一个字符是字母时,就需要判断是否和字符串 s 的 i 位置字符相等,相等的话就可以根据 dp[i - 1][j - 1] 来更新状态,如果是 ' . ' 的话,直接可以根据 dp[i - 1][j - 1] 来更新状态,如果是 ' * ' 的话,就需要考虑前一个字符是字母还是 ' . ',如果是 ' . ' 的话,就可以选择匹配空串,或者多个字符,就能更新出一堆状态,对于这样的状态表示,可以用上一题一样的优化方式,优化为 dp[i - 1][j] ,如果是字母的话,就需要判断是否能和 i 位置字符相等,然后选择匹配几个,同理,这种状态表示也可以优化为 dp[i - 1][j]
初始化:
第一列,也就是 p 是空串,这样除非 s 也是空串,否则怎么也不会匹配成功,所以只有 dp[0][0] 是 true,而对于第一行,如果说连续的偶数位上的字符是 ' * ' 的话,那么就可以带上前面的字符一起匹配空串,只要发现不是连续的偶数位,后面就都是 false
填表顺序:从上到下,从左到右
返回值:dp[m][n]
class Solution {
public boolean isMatch(String ss, String pp) {
int m = ss.length(),n = pp.length();
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
boolean[][] dp = new boolean[m + 1][n + 1];
//初始化
for (int i = 2; i <= n; i += 2){
if(p[i] == '*'){
dp[0][i] = true;
}else{
break;
}
}
dp[0][0] = true;
//填表
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
if (p[j] == '*'){
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 1] == '.' ||p[j - 1] == s[i]));
}else{
dp[i][j] = dp[i - 1][j - 1] && (p[j] == s[i] || p[j] == '.');
}
}
}
return dp[m][n];
}
}
6. 交错字符串
97. 交错字符串
状态表示:
为了方便进行表示,可以把三个字符串前面都加上一个空串,来更好的进行初始化和状态表示
dp[i][j] 表示 s1 中 [1 , i ] 区间内的字符串以及 s2 [ 1 , j ] 区间内的字符串,能否拼接成 s3 [1 , i + j ] 区间内的字符串
状态转移方程:
如果能拼接成功的话, s3 的最后一个位置一定是 s1 或者 s2 的最后一个字符,所以就可以分为两种情况,如果是 s1 的话,那么 dp[i][j] 就等于 dp[i - 1][j],同理,如果是 s2 的话,那么就是 dp[i][j - 1]
初始化:
初始化的时候,dp[0][i] 就表示 s1 是空串的情况,此时就是判断 s2 和 s3 各个位置上的字符是否相等,当遇到不相等的,后面所有的位置就都是 false, 同理,dp[i][0] 就表示 s2 是空串的情况
填表顺序:填当前位置时需要用到上一个位置的值,所以从上往下,从左往右依次填表
返回值:dp[m][n]
还有一个注意点就是,刚开始一定要判断如果 s1 和 s2 的长度和如果和 s3 的长度不相等就直接返回 false,不只是优化的问题,如果不添加的话,后续的填表也会有问题的
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 i = 1; i <= n; i++) {
if (s2.charAt(i) == s3.charAt(i)){
dp[0][i] = true;
}else{
break;
}
}
for(int i = 1;i <= m;i++){
if(s1.charAt(i) == s3.charAt(i)){
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) == s3.charAt(i + j) && dp[i - 1][j])||
(s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
}
}
return dp[m][n];
}
}
7. 两个字符串的最小ASCII删除和
712. 两个字符串的最小ASCII删除和
题中要求的是最小的 ASCII 删除和使剩下的字符串相等,那么就可以转化为公共子序列中最大的 ASCII 和,这样删除的 ASCII 和肯定就是最小的
状态表示:
dp[i][j] 表示 s1 的 [0 , i ] 区间和 s2 [0 , j ] 区间内的所有子序列中,公共子序列的 ASCII 最大和
状态转移方程:
可以分为四种情况,公共子序列中同时含有 s1 和 s2 的 i , j 位置的字符,以及只含其中一个,还有都不含的情况,由于是找最大值,都不包含的情况是被包含到只含一个的情况的,所以只需要求出前面三种情况的最大值即可
填表顺序:从左到右,从上到下
返回值:需要求出两个字符串的 ASCII 和,然后减去两倍的最大公共子序列的 ASCII 和
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(),n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
if(s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + s1.charAt(i - 1));
}
}
int sum = 0;
for(char c : s1.toCharArray()) sum += c;
for(char c : s2.toCharArray()) sum += c;
return sum - 2 * dp[m][n];
}
}