Interleaving String

 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

 

typedef struct ConflictPoint {
    int i;
    int j;
    int k;
    int flag; // 1 means go from s1 before, while 2 means s2
    ConflictPoint(int i, int j, int k):i(i), j(j), k(k) {}
} CP;

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.size();
        int l2 = s2.size();
        int l3 = s3.size();
        if(l1 + l2 != l3) return false;
        
        int i = 0, j = 0, k = 0;
        stack<CP> sp;
        
        for(; k < l3;) {
            bool conflict = false;
            if(s3[k] == s1[i] && s3[k] == s2[j]) {
                CP cp(i, j, k);
                sp.push(cp);
                conflict = true;
            }
            
            if(s3[k] == s1[i]) {
                ++k;
                ++i;
                if(conflict) sp.top().flag = 1;
            } else if(s3[k] == s2[j]) {
                ++k;
                ++j;
                if(conflict) sp.top().flag = 2;
            } else {   
                if(!sp.empty()) {
                    CP cp = sp.top();
                    sp.pop();
                    i = cp.i;
                    j = cp.j;
                    k = cp.k;
                    if(cp.flag == 1) {
                        ++k;
                        ++j;
                    } else if(cp.flag == 2) {
                        ++k;
                        ++i;
                    }
                } else {
                    return false;
                }
            }
        }
        
        return true;
    }
};

 

 欢迎关注微信公众号——计算机视觉