💕"往前走"💕
作者：Mylvzi
文章主要内容：算法系列–两个数组的dp问题(2)
大家好,今天为大家带来的是
算法系列--两个数组的dp问题(2),今天的题目相较于(1)简单很多
1.交错字符串
链接:
https://leetcode.cn/problems/interleaving-string/description/
分析:
本题看起来和之前做过的题目有所不同,这里一共有三个字符串,但是实际上只有两个字符串,当s1字符串的位置和s2字符串的位置固定之后,s3也就固定了,所以我们只需研究s1,s2这两个字符串即可
- 状态表示:
两个子串这样的问题最常用的状态表示就是s1在[0,i]区间内xxxx,s2[0,j]区间内xxxx,本题也是.dp[i][j]: s1在[0,i]区间内的字符串和s2在[0,j]区间内的字符串能否拼接成s3 - 状态转移方程的推导:往往是根据
最后一个位置的状态划分,分析如下:
s1[i] != s3[i + j] && s2[j] != s3[i + j],则根本无法拼接成s3–>falses1[i] == s3[i + j] || s2[j] == s3[i + j],只要其中有一个等于s3[i + j]就有可能拼接成s3,此时需要判断的是前一个位置能否拼接成s3,前一个位置成立,当前位置也成立;前一个位置不成立,当前位置也无法成立
- 初始化:还是根据状态表示去进行初始化
第一行:表示s1为空,则s1和s2要想拼接成s3,必须保证s2和s3完全相同
第一列:表示s2为空,则s1和s2要想拼接成s3,必须保证s1和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) == s3.charAt(j)) dp[0][j] = 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];// 返回值 } }
算法系列--两个数组的dp问题(2)（下）https://developer.aliyun.com/article/1480833?spm=a2c6h.13148508.setting.17.361f4f0eyTL4lb
