利用动态规划的思想, 对于每种状态(i, j)来说都有(i-1, j) 和 (i,j-1)
需要注意的问题 : 初始化的问题,先把i=0和j=0的状态都初始化后才可以进行dp否则发生数组越界
这里学到了一波vector的初始化方法 :
| 方法 | 解释 |
|---|---|
| vector< int > v | 默认初始化，vector为空， size为0 |
| vector< int > v2(v1) | vector v2 = v1 ; v2作为v1的copy |
| vector< int > v = {1,2,3} | 初始化为列表中元素的拷贝 |
| vector< int > v(x,y) | 初始化x个元素, 初值为y |
| vector< int > v(x) | 初始化x个元素, (int情况下)初值为0 |
| vector< vector< int > > v | 二维vector |
| vector< vector< int > > v(x,vector< int >(y,z)) | 有点绕,这么理解就好\(v[ x ][ y ]=z\) |
写出状态更新规则即可
#include<bits/stdc++.h>
using namespace std;
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
if(len1 + len2 != len3)
return false;
vector< vector<bool> > dp(len1+1, vector<bool>(len2+1, false)); // s1的前i个和s2的前j个是否可以成为s3的前i+j个
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];
}
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int t;
cin >> t;
while(t--){
string s1, s2, s3;
cin>>s1>>s2>>s3;
cout<<isInterleave(s1,s2,s3)<<endl;
}
return 0;
}