Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example
For s1 = "aabcc", s2 = "dbbca"
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

http://www.lintcode.com/en/problem/interleaving-string/

Discussion

设状态f[i][j]，表示s1[0,i] 和s2[0,j]，匹配s3[0, i+j]。如果s1 的最后一个字符等 于s3 的最后一个字符，则f[i][j]=f[i-1][j]；如果s2 的最后一个字符等于s3 的最后一个字符， 则f[i][j]=f[i][j-1]。因此状态转移方程如下：
f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);

Solution

class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        if(s3.length() != s1.length()+s2.length())
            return false;
        vector<vector<bool> > f(s1.length()+1, vector<bool>(s2.length()+1, true));
        for(int j=1; j<=s2.length(); j++) {
            f[0][j] = s2[j-1] == s3[j-1] &&f[0][j-1];
        }
        for(int i=1; i<=s1.length(); i++) {
            f[i][0] = s1[i-1] == s3[i-1] &&f[i-1][0];
        }
        for(int i=1; i<=s1.length(); i++) {
            for(int j=1; j<=s2.length(); j++) {
                if((s1[i-1] == s3[i+j-1] && f[i-1][j])
                    || (s2[j-1] == s3[i+j-1] && f[i][j-1])) {
                        f[i][j] = true;
                    } else {
                        f[i][j] = false;
                    }
            }
        }
        return f[s1.length()][s2.length()];
    }

};

递归解法，会超时。

class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        if(s3.length() != s1.length()+s2.length())
            return false;
        return interleave(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin(), s3.end());
    }
private:
    bool interleave(string::iterator s1start, string::iterator s1end, 
        string::iterator s2start, string::iterator s2end, 
        string::iterator s3start, string::iterator s3end) {
            if(s3start == s3end) {
                return (s1start==s1end && s2start==s2end);
            }
            if(*s3start == *s1start) {
                return interleave(next(s1start), s1end, s2start, s2end, next(s3start), s3end);
            }
            if(*s3start == *s2start) {
                return interleave(s1start, s1end, next(s2start), s2end, next(s3start), s3end);
            }
            return false;
        }
};

kamyu104's solution:

// Time:  O(m * n)
// Space: O(min(m, n))

// DP with rolling window.
class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // Early return if |s1| + |s2| != |s3|.
        if (s1.size() + s2.size() != s3.size()) {
            return false;
        }

        if (s1.size() < s2.size()) {
            return isInterleave(s2, s1, s3);
        }

        vector<deque<bool>> T(2, deque<bool>(s2.size() + 1));
        T[0][0] = true;  // Base case.

        // Uses chars from s2 only to match s3.
        for (size_t j = 0; j < s2.size(); ++j) {
            if (s2[j] == s3[j]) {
                T[0][j + 1] = true;
            } else {
                break;
            }
        }

        for (size_t i = 0; i < s1.size(); ++i) {
            // Uses chars from s1 only to match s3.
            T[(i + 1) % 2][0] = T[i % 2][0] && s1[i] == s3[i];

            for (size_t j = 0; j < s2.size(); ++j) {
                T[(i + 1) % 2][j + 1] = (T[i % 2][j + 1] && s1[i] == s3[i + j + 1]) ||
                (T[(i + 1) % 2][j] && s2[j] == s3[i + j + 1]);
            }
        }

        return T[s1.size() % 2][s2.size()];
    }
};