https://oj.leetcode.com/problems/interleaving-string/
这种字符串的题目已经把DP或MEMO写在了脸上。
这题容易想到O(m1*m2*n)的DP方案,但这种方法有很多空间和时间的浪费。需要注意到我们在递推的比较过程中如果知道s1,s2上的指针p,q的情况,s3上这个指针肯定在p+q的位置。利用这个结论,就可以设计出O(m1*m2)的DP方案。
递推关系如下:
f(p,q): s1前p个字符子串和s2前q个字符子串能否match到s3前(p+q)个字符子串?
同LCS问题一样,考察此时的s[p-1]和s[q-1]以及s3[p+q-1]的关系,考察是否能够找到匹配的方案。
代码如下:
class Solution {
public:
string s1,s2,s3;
int m1,m2,n;
vector <vector<bool>> dp;
bool isInterleave(string s1, string s2, string s3) {
n=s3.length();
m1=s1.length();
m2=s2.length();
if (m1+m2!=n){return false;}
dp.resize(m1+1,vector<bool>(m2+1,false));
dp[0][0]=true;
for (int i=0;i<=m1;i++){
for (int j=0;j<=m2;j++){
if (i==0 && j==0){continue;}
if (i>0){
if (s1[i-1]==s3[i+j-1]){
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
if (j>0){
if (s2[j-1]==s3[i+j-1]){
dp[i][j] = dp[i][j] ||dp[i][j-1];
}
}
}
}
return dp[m1][m2];
}
};