给定三个字符串 s1 , s2 , s3 ,请你验证 s3 是否是 s1 和 s2 交错组成。
交错组成的定义是,把 s1 和 s2 分别拆分成子串 a1+a2+a3..+an , b1+b2+b3+..+bn , a1+b1+a2+b2+... 或 b1+a1+b2+a2+... 可以组成 s3 就定义为交错组成。
数据范围:字符串的长度满足
"abc","defgh","abcdef"
false
"abd","cefgh","abcdefgh"
true
ab+c+d+efgh
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s1 string字符串 * @param s2 string字符串 * @param s3 string字符串 * @return bool布尔型 */ bool stringJudge(string s1, string s2, string s3) { // write code here /* dp[i][j] 表示s1的前i个字符和s2的前j个字符能否组成s3前i+j个字符 两种情况 1、s1的第i个字符和s3的第i+j-1相等 且dp[i - 1][j]为真 则此时可组成s3前i+j个字符 2、s2的第j个字符和s3的第i+j-1相等 且dp[i][j - 1]为真 则此时可组成s3前i+j个字符 */ int n1 = s1.size(), n2 = s2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, false)); dp[0][0] = true; // 从0开始遍历 到n1 for(int i = 0; i <= n1; i++) { for(int j = 0; j <= n2; j++) { int index = i + j - 1; if(i > 0) { dp[i][j] |= (dp[i - 1][j] && s1[i - 1] == s3[index]); } if(j > 0) { dp[i][j] |= (dp[i][j - 1] && s2[j - 1] == s3[index]); } } } return dp[n1][n2]; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s1 string字符串 * @param s2 string字符串 * @param s3 string字符串 * @return bool布尔型 */ bool f[2010][2020]; bool stringJudge(string s1, string s2, string s3) { if(s1.size()+s2.size()!=s3.size())return false; // write code here memset(f,0,sizeof f); f[0][0]=true; for(int i=1;i<=s3.size();++i){ for(int j=0;j<=s1.size()&&j<=i;++j){ if(j!=0)//s1[j-1]匹配 [j,i-1-j] f[i][j]|=(s3[i-1]==s1[j-1]&&f[i-1][j-1]); if(i!=j)//[j-1,i-j] f[i][j]|=(s3[i-1]==s2[i-j-1]&&f[i-1][j]); // cout<<i<<" "<<j<<" "<<f[i][j]<<endl; } } return f[s3.size()][s1.size()]; } };