LeetCode 97. 交错字符串

LeetCode 97. 交错字符串

思路：
f[i][j]状态表示为是否可以交错拼成s3，集合划分以s3最后一个字符串的来源划分，状态计算为f[i][j] = f[i-1][j] || f[i][j-1]，第一种需要保证s3[i+j] == s[i],第二种需要保证s3[i+j] == s2[j]。

这道题用双指针是错的，因为对于s3的某个字符来说，可能此时s1与s2都可以凑出来这个字符，但是一旦选错了，最后就不能恰好的拼成s3。

代码：

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