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.

Link to the explanation graph

/*passed small test, but did not pass large test.
It is slow due to the overlapping subproblems, and 
it run in exponential time.
 See below for the faster solution.
*/

class Solution {
private:
    bool build(string const& a, string const& b, string const& c,
        int const aii, int const bii){//true-a, false-b
          if (aii < 0 && bii < 0) return true;
          if (aii < 0){
              if (b[bii] != c[aii+bii+1]) return false;
              else return build(a,b,c,aii,bii-1);
          }
          if (bii < 0){
              if (a[aii] != c[aii+bii+1]) return false;
              else return build(a,b,c,aii-1,bii);
              
          }
          if (b[bii] != c[aii+bii+1] && a[aii] != c[aii+bii+1]) return false;
          bool ra=false, rb=false;
          if (a[aii] == c[aii+bii+1]) ra= build(a,b,c,aii-1,bii);
          if (b[bii] == c[aii+bii+1]) rb= build(a,b,c,aii,bii-1);
          return ra||rb;
        }
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.empty() || s2.empty()) return (!s1.compare(s3) || !s2.compare(s3));
        return build(s1,s2,s3,s1.length()-1,s2.length()-1);
    }
};

/**The one below works for both small and large cases
*/
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.empty() || s2.empty()) return (!s1.compare(s3) || !s2.compare(s3));

        s1 = "S"+s1;
        s2 = "S"+s2;
        s3 = "S"+s3;//index starts from 1
        vector<vector<bool> > v(s1.length()+1, vector<bool>(s2.length()+1, false));
        v[0][0]=true;
        for(int ii = 1; ii < s2.length(); ++ii){
            if (s2[ii] == s3[ii]) v[0][ii] = v[0][ii-1];
        }
        for(int ii = 1; ii < s1.length(); ++ii){
            if (s1[ii] == s3[ii]) v[ii][0] = v[ii-1][0];
        }
        for(int ii = 1; ii <s1.length(); ++ii){
            for(int jj = 1; jj <s2.length(); ++jj){
                if (s1[ii] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii-1][jj];
                if (s2[jj] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii][jj-1];
            }
        }
        return v[s1.length()-1][s2.length()-1];
    }
};