给出三个字符串s1, s2, s3,判断s3是否可以由s1和s2交织而成。
例如：
给定
s1 ="xxyzz",
s2 ="pyyzx",
s2 ="pyyzx",
如果s3 ="xxpyyzyzxz", 返回true
如果s3 ="xxpyyyxzzz", 返回false
[编程题]交织的字符串
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1+len2 !=len3){
return false;
}
char[] chs1 = s1.toCharArray();
char[] chs2 = s2.toCharArray();
char[] chs3 = s3.toCharArray();
//dp[i][j]代表 chs1[0...i] chs2[0...j]能否顺序匹配chs3[i+j]
boolean[][] dp = new boolean[len1+1][len2+1];
//初始化 s1中取0个字符 s2中取0个字符 匹配s3从0开始的0个字符 肯定匹配true
dp[0][0] = true;
//s1中取0个s2中取i个 去和s3中0+i 个匹配
for(int i = 1 ; i < len2 + 1; i ++ ){
dp[0][i] = dp[0][i-1] && chs2[i-1] == chs3[i-1];
}
//s2中取0个s1中取i个 去和s3中0+i 个匹配
for(int i = 1 ; i < len1 + 1; i ++ ){
dp[i][0] = dp[i-1][0] && chs1[i-1] == chs3[i-1];
}
for(int i = 1 ; i < len1+1 ; i ++ ){
for(int j = 1 ; j < len2+1 ; j ++ ){
dp[i][j] = dp[i-1][j] && (chs3[i+j-1] == chs1[i-1])
|| dp[i][j-1] && (chs3[i+j-1] == chs2[j-1]);
}
}
return dp[len1][len2];
}
}
发表于 2016-05-17 19:38:05
回复(7)
s3是由s1和s2交织生成的，意味着s3由s1和s2组成，在s3中s1和s2字符的顺序是不能变化的，和子序列题型类似，这种题我们一般是用动态规划来解。
- 设dp[i][j]表示s3的前i+j个字符可以由s1的前i个字符和s2的前j个字符交织而成。
- 状态转移方程：有两种情况
- 第一个状态转移方程：
dp[i][j]= {(dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i-1个字符和s2的前j个字符交织而成，那么只需要s1的第i个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true; - 第二个状态转移方程：
dp[i][j]= {(dp[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i个字符和s2的前j-1个字符交织而成，那么只需要s2的第j个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true;
- 第一个状态转移方程：
作者：yoshino
链接：http://www.jianshu.com/p/1e991930e44f
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
发表于 2017-08-26 21:57:29
回复(1)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l1+l2 != l3)
return false;
vector<vector<bool> > dp(l1+1,vector<bool>(l2+1,false));
dp[0][0] = true;
for(int i=1;i<=l1;i++)
dp[i][0] = dp[i-1][0] && s1[i-1]==s3[i-1];
for(int j=1;j<=l2;j++)
dp[0][j] = dp[0][j-1] && s2[j-1]==s3[j-1];
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1] ||
dp[i][j-1] && s2[j-1]==s3[i+j-1]);
return dp[l1][l2];
}
};
发表于 2017-09-30 01:12:41
回复(0)
public class Solution {
//二维动态规划
public boolean isInterleave(String s1, String s2, String s3) {
if(s1 == null || s2 == null || s3 == null){
return false;
}
int len1 = s1.length(),len2 = s2.length(),len3 = s3.length();
if(len3 != len1+len2){
return false;
}
boolean[][] dp = new boolean[len1+1][len2+1];
for(int i = 0 ; i <= len1 ; i++){
for(int j = 0 ; j <=len2 ; j++){
dp[i][j] = i==0&&j==0 ? true : (i-1 >= 0 && dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (j-1 >=0 && dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));
}
}
return dp[len1][len2];
}
}
发表于 2018-03-22 01:27:44
回复(0)
class Solution {
public:
// dp[i][j] 使用s1[0,1,...,i]字符串和s2[0,1,2,...,j]字符串，组合成s3(i+j)
bool isInterleave(string s1, string s2, string s3)
{
int m=s1.length(),n=s2.length(),l=s3.length();
if(m+n != l)
return false;
vector<vector<bool> > dp(m+1,vector<bool>(n+1,false));
dp[0][0] = true;
for(int i=1;i<=m;i++)
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
for(int j=1;j<=n;j++)
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) ||
(dp[i][j-1] && s2[j-1] == s3[i+j-1]);
}
}
return dp[m][n];
}
};
发表于 2017-07-11 17:39:00
回复(0)
//递归版，也是动态规划的思路但是没用额外的二维数组去保存信息
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int l1=s1.size();
int l2=s2.size();
int l3=s3.size();
if(l1+l2!=l3){
return false;
}
if(l1 == 0&&l2==0&&l3==0){
return true;
}
return Helper(s1,s2,s3,l1-1,l2-1);
}
private:
bool Helper(const string& s1, const string& s2, const string& s3,int l1,int l2){
bool r1,r2;
if(l1<0&&l2>=0){
for(int i=0;i<=l2;i++){
if(s2[i]!=s3[i]){
return false;
}
}
return true;
}
else if(l2<0&&l1>=0){
for(int i=0;i<=l1;i++){
if(s1[i]!=s3[i]){
return false;
}
}
return true;
}
return (s3[l1+l2+1]==s1[l1]&&Helper(s1,s2,s3,l1-1,l2))||(s3[l1+l2+1]==s2[l2]&&Helper(s1,s2,s3,l1,l2-1));
}
};
public:
bool isInterleave(string s1, string s2, string s3) {
int l1=s1.size();
int l2=s2.size();
int l3=s3.size();
if(l1+l2!=l3){
return false;
}
if(l1 == 0&&l2==0&&l3==0){
return true;
}
return Helper(s1,s2,s3,l1-1,l2-1);
}
private:
bool Helper(const string& s1, const string& s2, const string& s3,int l1,int l2){
bool r1,r2;
if(l1<0&&l2>=0){
for(int i=0;i<=l2;i++){
if(s2[i]!=s3[i]){
return false;
}
}
return true;
}
else if(l2<0&&l1>=0){
for(int i=0;i<=l1;i++){
if(s1[i]!=s3[i]){
return false;
}
}
return true;
}
return (s3[l1+l2+1]==s1[l1]&&Helper(s1,s2,s3,l1-1,l2))||(s3[l1+l2+1]==s2[l2]&&Helper(s1,s2,s3,l1,l2-1));
}
};
发表于 2018-03-15 16:12:18
回复(0)
感觉这种dp题找不到状态转移方程的话，就自己画一个dp二维矩阵，画着画着就找的着规律了。。。
public class Solution {
//dp题，求字符串S1与字符串s2交叉能否得到串S3，dp表示字符串s1的前i个字符和字符串的前j个字符能否组成字符串S3的前i+j个字符。
public boolean isInterleave(String s1, String s2, String s3) {
//先考虑特殊情况
if((s1.length()+s2.length())!=s3.length())
return false;
int [][]dp=new int[s1.length()+1][s2.length()+1];
//初始化
for(int i=1;i<=s2.length();i++) {
dp[0][i]=(s2.charAt(i-1)==s3.charAt(i-1)?1:0);
if(dp[0][i]==0)//后面不会再相等
break;
}
for(int j=1;j<=s1.length();j++) {
dp[j][0]=(s1.charAt(j-1)==s3.charAt(j-1)?1:0);
if(dp[j][0]==0)
break;
}
dp[0][0]=1;
for(int i=1;i<=s1.length();i++) {
for(int j=1;j<=s2.length();j++) {
if(dp[i-1][j]==1 && s3.charAt(i+j-1)==s1.charAt(i-1)) {
dp[i][j]=1;
}
else if(dp[i][j-1]==1 && s3.charAt(i+j-1)==s2.charAt(j-1)) {
dp[i][j]=1;
}else {
dp[i][j]=0;
}
}
}
return dp[s1.length()][s2.length()]==1?true:false;
}
}
发表于 2020-04-14 15:06:23
回复(0)
/*
* 目的：判断s3是否可以由s1和s2交织而成。
* 方法：动态规划
*/
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();
int n2 = s2.size();
int n3 = s3.size();
if (n1+n2!=n3) return false;
vector<vector<bool>>dp(n1+1,vector<bool>(n2+1, false));
dp[0][0] = true;
for (int i = 1; i<=n1;++i){
dp[i][0] = dp[i-1][0] &&(s1[i-1] == s3[i-1]);
}
for (int j = 1; j <=n2;++j){
dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]);
}
for (int i = 1; i <=n1; ++i){
for (int j = 1; j<=n2; ++j){
dp[i][j] = dp[i-1][j] && (s1[i-1] == s3[i + j-1]) ||
dp[i][j-1] && (s2[j-1]== s3[i+j-1]);
}
}
return dp[n1][n2];
}
发表于 2019-12-08 14:58:18
回复(0)
交错的字符串interleaving-string
思路：暴力递归 or 动态规划
解法一：暴力递归（会超时）
- 维护三个指针p1,p2,p3，分别指向s1,s2,s3当前的位置
- 若p1还未超出s1长度且p1指向的字符和s3指向的字符相等，将p1+1且p3+1进行递归
- 若p2还未超出s2长度且p2指向的字符和s3指向的字符相等，将p2+1且p3+1进行递归
代码
public boolean isInterleave(String s1, String s2, String s3) {
return dfs(s1,s2,s3,0,0,0);
}
public boolean dfs(String s1,String s2,String s3,int p1,int p2,int p3){
if(p1==s1.length()&&p2==s2.length()&&p3==s3.length())
return true;
boolean b1 = false;
boolean b2 = false;
if(p1<s1.length()&&p3<s3.length()&&s3.charAt(p3)==s1.charAt(p1))
b1 = dfs(s1,s2,s3,p1+1,p2,p3+1);
if(p2<s2.length()&&p3<s3.length()&&s3.charAt(p3)==s2.charAt(p2))
b2 = dfs(s1,s2,s3,p1,p2+1,p3+1);
return b1||b2;
} 解法二：动态规划
- 1.创建一个二维boolean数组dp[][],dp[ i ][ j ]表示s1前i个字符和s2前j个字符是否可以交织成s3前i+j个字符
- 可以根据上面的暴力递归的递归式得到状态转换方程
- dfs(s1,s2,s3,p1+1,p2,p3+1) ---> dp[ i ][ j ]=dp[ i-1 ][ j ]&&s1.charAt(i-1) == s3.charA(i+j-1)
- dfs(s1,s2,s3,p1+1,p2,p3+1) ---> dp[ i ][ j ]=dp[ i ][ j-1 ]&&s2.charAt(j-1) == s3.charA(i+j-1)
注意：34两个dp式子是表示，s1前i个字符和s2前j个字符能否交织成s3前i+j个字符是由下面两种情况决定的:
- s1前i-1个和s2前j个字符能否交织成s3前i+j-1个字符，且，s1的第i个字符是否等于s3的第i+j个字符？所以charAt(i-1)中的i-1和dp中的i-1是不同的，因为string是从0开始算，所以要减1
- s1前i个和s2前j-1个字符能否交织成s3前i+j-1个字符，且，s2的第j个字符是否等于s3的第i+j个字符？
如果以上两种情况有一种为true，那么dp[ i ] [ j ]就为true
还有一个要注意的，dp[ 0 ][ 0 ]表示空字符串和空字符串能否匹配前0个字符，答案是肯定的，所以要初始化为0。那么对应的，dp[ 0 ][ j ]和dp[ i ][ 0 ]也要对应初始化一下
代码
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length())
return false;
boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
dp[0][0] = true;
for(int i=1;i<dp[0].length;i++)
dp[0][i] = dp[0][i-1]&&s2.charAt(i-1)==s3.charAt(i-1);
for(int i=1;i<dp.length;i++)
dp[i][0] = dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
for(int i=1;i<dp.length;i++)
for(int j=1;j<dp[0].length;j++){
dp[i][j]=dp[i-1][j]&&(s1.charAt(i-1)==s3.charAt(i+j-1))||dp[i][j-1]&&(s2.charAt(j-1)==s3.charAt(i+j-1));
}
return dp[s1.length()][s2.length()];
}
}
发表于 2019-08-22 12:39:29
回复(0)
/***
菜鸡的我只能写个递归版
*/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {if(s1==null||s2==null||s3==null) return false;
if(s1.length()+s2.length()!=s3.length()) return false;
return isInterleave(s1,s1.length()-1,s2,s2.length()-1,s3,s3.length()-1);
}
public boolean isInterleave(String s1, int i, String s2, int j, String s3, int k){
if(i<0&&j<0) return true;
if(i<0){
if(s2.charAt(j) != s3.charAt(k))
return false;
return isInterleave( s1, i, s2, j-1, s3, k-1 );
}
if(j<0){
if(s1.charAt(i) != s3.charAt(k))
return false;
return isInterleave( s1, i-1, s2, j, s3, k-1 );
}
if(s3.charAt(k)!=s1.charAt(i)&&s3.charAt(k)!=s2.charAt(j))
return false;
if(s1.charAt(i)==s2.charAt(j)){
return isInterleave( s1, i, s2, j-1, s3, k-1 )||isInterleave( s1, i-1, s2, j, s3, k-1 );
}else{
if(s1.charAt(i)==s3.charAt(k))
return isInterleave( s1, i-1, s2, j, s3, k-1 );
else
return isInterleave( s1, i, s2, j-1, s3, k-1 );
}
}
}
发表于 2019-07-11 11:46:13
回复(0)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length()) return false;
boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
dp[0][0]=true;
for(int i=0,j=1;j<=s2.length();j++) dp[i][j]=(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(j-1));
for(int i=1,j=0;i<=s1.length();i++) dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i-1));
for(int i=1;i<=s1.length();i++) {
for(int j=1;j<=s2.length();j++) {
dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
}
}
return dp[s1.length()][s2.length()];
}
}
发表于 2019-05-01 19:52:59
回复(0)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s3.size();
int s1n = s1.size();
int s2n = s2.size();
if(n <= 0 && s1n <=0 && s2n <=0 ) return true;
if( n != s1n + s2n) return false;
bool dp[n+1][n+1];
for(int i = 0; i < n + 1 ; i++)
for(int j = 0; j < n + 1; j++)
dp[i][j] = false;
if(s1n > 0 && s1[0] == s3[0]) dp[1][0] = true;
if(s2n > 0 && s2[0] == s3[0]) dp[0][1] = true;
for(int l = 2; l <= n ; l++){
for(int i = 0; i <= l - 1; i ++){
if(dp[i][l-i-1] && s3[l-1] == s1[i]) dp[i+1][l-i-1] = true;
if(dp[i][l-i-1] && s3[l-1] == s2[l-i-1]) dp[i][l-i] = true;
}
}
return dp[s1n][s2n];
}
};
// dp[i][j] 表示s1的前i长度与s2的前j长度能否组合成s3的i+j长度
//例如：
// s1 = "aabcc"
// s2 = "dbbca"
// s3 = "aadbbcbcac"
// dp[4][3]表示s1的前4长度 "aabc" 与
// s2的前3长度 "dbb"
// 能否组合成s3的前5长度"aadbbc"
编辑于 2019-04-06 18:28:12
回复(0)
//典型的二维动态规划问题，动态规划好像都是一个模式我觉得，假如用i,j分别代表s1,s2字符串的取值
//下标，则可以通过dp[i][j]来判断s3字符串的前i+j（这里只是示意，不考虑下标是不是从0开始）的字符
//能不能得到，题中的意思就是通过s1,s2互相插入(有顺序的，所以能用动规)，判断能不能得到s3
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1+len2 != len3)
return false;
vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));
dp[0][0] = true;
for(int i=1;i<=len1;i++)
dp[i][0] = dp[i-1][0] && (s1[i-1]==s3[i-1]);
for(int j=1;j<=len2;j++)
dp[0][j] = dp[0][j-1] && (s2[j-1]==s3[j-1]);
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
dp[i][j] = (dp[i][j-1]&&(s2[j-1]==s3[i+j-1])) || (dp[i-1][j]&&(s1[i-1]==s3[i+j-1]));
}
}
return dp[len1][len2];
}
};
发表于 2018-12-07 11:20:42
回复(0)
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
boolean[][] res = new boolean[s1.length() + 1][s2.length() + 1];
res[0][0] = true;
for (int i = 0; i < s1.length(); i++) {
res[i + 1][0] = res[i][0] && s1.charAt(i) == s3.charAt(i);
}
for (int i = 0; i < s2.length(); i++) {
res[0][i + 1] = res[0][i] && s2.charAt(i) == s3.charAt(i);
}
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
res[i + 1][j + 1] = (res[i][j + 1] && s1.charAt(i) == s3.charAt(i + j + 1))
|| (res[i + 1][j] && s2.charAt(j) == s3.charAt(i + j + 1));
}
}
return res[s1.length()][s2.length()];
}
发表于 2017-07-13 10:14:39
回复(0)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// 边界条件判定
if(s3 == null && (s1 != null || s2 != null))
return false;
if((s1 == null && s2 == null) && s3 != null)
return false;
if(s1 == null && s2 == null && s3 == null)
return true;
if(s1.length() + s2.length() != s3.length())
return false;
// dp[i][j]代表s1的0~i,s2的0~j，能否匹配s3的i+j
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for(int i = 1; i < dp.length; i++){
if(dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1))
dp[i][0] = true;
}
for(int j = 1; j < dp[0].length; j++){
if(dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1))
dp[0][j] = true;
}
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp[0].length; j++){
if(dp[i][j-1]){
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp[i][j] = true;
}
else if(dp[i-1][j]){
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp[i][j] = true;
}
}
}
return dp[s1.length()][s2.length()];
}
}
发表于 2017-05-22 22:26:09
回复(0)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for (int i = 1; i < dp.length; i ++ ) {
dp[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i < dp[0].length; i ++ ) {
dp[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i < dp.length; i ++ ) {
for (int j = 1; j < dp[0].length; j ++ ) {
if(s3.charAt(i + j - 1) == s1.charAt(i - 1) && dp[i - 1][j]) dp[i][j] = true;
else if(s3.charAt(i + j - 1) == s2.charAt(j - 1) && dp[i][j - 1]) dp[i][j] = true;
}
}
return dp[s1.length()][s2.length()];
}
}
发表于 2016-11-22 18:06:20
回复(0)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size()) return false;
if(s3.empty()) return true;
vector<vector<bool> > dp(s1.size()+1, vector<bool>(s2.size()+1, false));
dp[0][0] = true;
for(int i = 0; i < s1.size(); i++) {
if(s1[i] != s3[i]) break;
dp[i+1][0] = true;
}
for(int i = 0; i < s2.size(); i++) {
if(s2[i] != s3[i]) break;
dp[0][i+1] = true;
}
for(int i = 1; i <= s1.size(); i++) {
for(int j = 1; j <= s2.size(); j++) {
if((dp[i-1][j] && s3[i+j-1] == s1[i-1]) ||
(dp[i][j-1] && s3[i+j-1] == s2[j-1])) {
dp[i][j] = true;
}
}
}
return dp[s1.size()][s2.size()];
}
}; 定义好状态就很直观了。
发表于 2020-11-11 17:27:10
回复(0)
"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：
- 如果S1[i]==S3[i+j+1]&&S2[j]!=S3[i+j+1]，那么dp[i+1][j+1] = dp[i][j+1]
- 如果S1[i]!=S3[i+j+1]&&S2[j]==S3[i+j+1]，那么dp[i+1][j+1] = dp[i+1][j][k+1]
- 如果S1[i]==S3[i+j+1]&&S2[j]==S3[i+j+1]，那么dp[i+1][j+1] = dp[i][j+1]||dp[i+1][j]
- 如果S1[i]!=S3[i+j+1]&&S2[j]!=S3[i+j+1]，那么dp[i+1][j+1] = false
- 基准1: dp[0][0]=true
- 基准2: dp[0][1..len2]和dp[1..len1][0]
注意：如果S1的最大下标为i，S2最大下标为j，那么合并S1和S2之后的最大下标为i+j+1
代码如下：
classSolution {
public:
/**
*
* @param s1 string字符串
* @param s2 string字符串
* @param s3 string字符串
* @return bool布尔型
*/
bool isInterleave(string s1, string s2, string s3) {
// write code here
inta = s1.size(), b = s2.size(), c = s3.size();
if(a + b != c) return false;
vector<vector<bool> > dp(a+1, vector<bool>(b+1, false));
dp[0][0] = true;
for(inti = 0; i < a && s1[i] == s3[i]; ++i) dp[i+1][0] = true;
for(inti = 0; i < b && s2[i] == s3[i]; ++i) dp[0][i+1] = true;
for(inti = 0; i < a; ++i) {
for(intj = 0; j < b; ++j) {
intm = s1[i], n = s2[j], o = s3[i+j+1];
if(m == o && n != o) dp[i+1][j+1] = dp[i][j+1];
if(m != o && n == o) dp[i+1][j+1] = dp[i+1][j];
if(m == o && n == o) dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j];
if(m != o && n != o) dp[i+1][j+1] = false;
}
}
return dp[a][b];
}
};
编辑于 2020-08-25 15:54:54
回复(0)
- 第一个状态转移方程：
dp[i][j]= {(dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i-1个字符和s2的前j个字符交织而成，那么只需要s1的第i个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true; - 第二个状态转移方程：
dp[i][j]= {(dp[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i个字符和s2的前j-1个字符交织而成，那么只需要s2的第j个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true;
vector<vector<int> > visited(row,vector<int>(column,6));//初始化一个 二维vector 行row,列column ,且 值为data=6 自定义data;
发表于 2020-04-20 11:46:00
回复(0)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int pos1,pos2,pos3;
pos1=0;pos2=0;pos3=0;
int len1=s1.size();
int len2=s2.size();
int len3=s3.size();
vector<int>flag(len3,0);
stack<int>path1;
stack<int>path2;
stack<int>path3;
while(pos3<len3)
{
if(pos1<len1&&pos2<len2&&s1[pos1]==s3[pos3]&&s2[pos2]==s3[pos3])
{
path3.push(pos3);
path2.push(pos2);
path1.push(pos1);
pos1++;
pos3++;
}
else if(pos1<len1&&s1[pos1]==s3[pos3])
{
pos1++;
pos3++;
}
else if(pos2<len2&&s2[pos2]==s3[pos3])
{
pos2++;
pos3++;
}
else
{
if(path3.empty())return false;
else
{
pos1=path1.top();
path1.pop();
pos2=path2.top();
path2.pop();
pos3=path3.top();
path3.pop();
pos2++;
pos3++;
}
}
}
return pos3==len3&&pos2==len2&&pos1==len1;
}
}; 看到大家都用的动态规划，我是个憨憨硬仿真，竟然过了，换成递归估计过不了，用的循环和栈结构
发表于 2020-03-13 21:46:13
回复(0)
问题信息
难度：
64条回答
147收藏
23143浏览
通过挑战的用户
查看代码-
2022-08-26 13:09:56
-
2022-08-20 14:48:58
-
2022-08-11 22:28:30 -
2022-07-20 15:02:39
-
2022-07-11 22:13:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
