[Leetcode] 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.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

k chars s3 could be an interleaving string of  i s1 chars and j s2 chars if i + j = k;  if we know the s3 is an interleaving string of s1 and s2, then if  s3[k+1] == s1[i+1] or s3[k+1] == s2[j+1],  s3 is also an interleaving string of s1 and s2 by simply appending s1[i+1] or s2[j+1] to s3. Based on the observation,  let f[i][j] be true if s3 is the interleaving string of first i chars of s1 and first  j chars of s2; and false otherwise, we can have the transition function:

f[i][j] = f[i-1][j] && s1.substr(i-1, 1) == s3.substr(i+j-1, 1) || f[i][j-1] & s2.substr(j-1, 1) == s3.substr(i+j-1, 1))
f[i][j]  = true, if I =0, j =0

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

//Solution 2: Recursive
bool isInterleaveHelper(string s1, int i, string s2, int j, string s3,int k) {
    if (k == s3.size())
        return true;
    else
    {
        if (s1[i] == s3[k] && s2[j] == s3[k])
            return isInterleaveHelper(s1, i+1, s2, j, s3, k+1) || isInterleaveHelper(s1, i, s2, j+1, s3, k+1);
        else if (s1[i] == s3[k])
            return isInterleaveHelper(s1, i+1, s2, j, s3, k+1);
        else if (s2[j] == s3[k])
            return isInterleaveHelper(s1, i, s2, j+1, s3, k+1);
        else
            return false;
    }
}

bool isInterleave(string s1, string s2, string s3) { 
    if (s1.size() + s2.size() != s3.size())
        return false;
    return isInterleaveHelper(s1, 0, s2, 0, s3, 0);
}