leetcode97. 交错字符串

分析

刚开始读完题目就想到了双指针，写完之后样例过不了，想了很久，没想明白错在哪里，看了题解用动态规划来着，大意是用f[i][j]表示s1[i]和s2[j]是否能合成s3[i+j]，若s1[i]==p[i+j],那么f[i][j]=true的条件是f[i-1][j]=true&&s1[i-1]==s3[i+j-1]，或者f[i][j-1]=true&&s2[j-1]==s3[i+j-1]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        vector < vector <int> > f(s1.size() + 1, vector <int> (s2.size() + 1, false));//生成f[n+1][m+1]默认为false的数组
        int n=s1.size(),m=s2.size(),t=s3.size();
        if(n+m!=t) return false;//长度不同必然是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>0){
                    f[i][j]|=f[i-1][j]&&s1[i-1]==s3[p];//s1匹配
                }
                if(j>0){
                     f[i][j]|=f[i][j-1]&&s2[j-1]==s3[p];//s[2]匹配
                }
            }
            return f[n][m];
    }
};

优化版

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        auto f = vector <int> (s2.size() + 1, false);

        int n = s1.size(), m = s2.size(), t = s3.size();

        if (n + m != t) {
            return false;
        }

        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] &= (s1[i - 1] == s3[p]);
                }
                if (j > 0) {
                    f[j] |= (f[j - 1] && s2[j - 1] == s3[p]);
                }
            }
        }

        return f[m];
    }
};