给定三个字符串 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
连接。
思路:
dp[i][j]表示s1的前i个字符,s2的前j个字符匹配s3的前i+j个字符是否有可以匹配成功,则dp[i][j]的组成可以是s1的前i-1个字符,s2的前j个字符加上s1的第i个字符。或者s1的前i个字符,s2的前j-1个字符加上s2的第j个字符。这么做的好处是限定了最后一个s1/s2要插入的字符是那个,将所有情况分成了两种,则dp[i][j]=dp[i][j-1] (当s2的第j个字符可以匹配时才有)||dp[i-1][j](当s1的第i个字符可以匹配才有)。
初始化:
多开一行一列,为了方便后续的统一。但由于多开了一列,需要进行一部分的初始化。如dp[0][0]表示空串,一定可以匹配成功,故为true,然后看i=0的情况和j=0的情况。当i等于0,则表示只用s2来匹配s3,故当从s2的(0-j)可以匹配成功时,才看s2的第j+1个元素是否可以匹配。对j等于0的情况同理。
整齐化:
由于多开了一行一列,故dp的下标对应s1,s2,s3的下标会出现差,因此可以在s1s2s3的前面均加一个空格,这样就会保证s1下标为i,s2下标为j时,对应的就是dp[i][j]。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1=s1.size(),n2=s2.size(),n3=s3.size();
if(n1+n2!=n3)
return false;
vector<vector<bool>>dp(n1+1,vector<bool>(n2+1));
s1=" "+s1,s2=" "+s2,s3=" "+s3;
//初始化
for(int i=1;i<=n1;i++)
{
if(s1[i]==s3[i])
{
dp[i][0]=true;
}
else
break;
}
for(int j=1;j<=n2;j++)
{
if(s2[j]==s3[j])
{
dp[0][j]=true;
}
else break;
}
dp[0][0]=true;
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
dp[i][j]= ( dp[i-1][j]&&s3[i+j]==s1[i])||(dp[i][j-1]&&s3[i+j]==s2[j]);
}
}
return dp[n1][n2];
}
};