动态规划

状态转移方程 f[[i,j]=f[i−1,j]∣∣f[i,j−1]f[[i,j] = f[i-1,j]\ ||\ f[i,j-1]f[[i,j]=f[i−1,j] ∣∣ f[i,j−1] ，仅当最后一个字符匹配。

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n = s1.size(),m = s2.size();if(n+m!=s3.size()) return false;s1 = ' '+s1,s2=' ' + s2,s3 = ' '+s3;vector> f(n+1,vector(m+1,false));for(int i = 0 ;i<=n;i++)for(int j = 0;j<=m;j++){if(!i&&!j) f[i][j] = true;else{if(i&&s1[i]==s3[i+j]) f[i][j] = f[i-1][j];if(j&&s2[j]==s3[i+j]) f[i][j] = f[i][j]||f[i][j-1];}}return f[n][m];}
};

1. 时间复杂度 : O(n2)O(n^2)O(n2) ，状态转移的时间复杂度 O(n2)O(n^2)O(n2) 。
2. 空间复杂度 : O(n2)O(n^2)O(n2) ，所有状态的空间复杂度 O(n2)O(n^2)O(n2) 。

AC