力扣(LeetCode)97. 交错字符串(C++)

动态规划

状态转移方程 $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<vector<bool>> f(n+1,vector<bool>(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

AC