97. 交错字符串

97. 交错字符串

dp

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