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.

Challenge

O(n^2) time or better

class Solution {
    bool helper(string s1, string s2, string s3)
    {
        if (s1.length() == 0) return s2 == s3;
        if (s2.length() == 0) return s1 == s3;
        
        return (s3[0] == s1[0] && helper(s1.substr(1), s2, s3.substr(1))) ||
                (s3[0] == s2[0] && helper(s1, s2.substr(1), s3.substr(1)));
    }
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) {
        char map[256] = {0};
        if (s1.length() + s2.length() != s3.length()) return false;
        for(char c: s1) map[c]++;
        for(char c: s2) map[c]++;
        for(char c: s3) {
            map[c]--;
            if (map[c] < 0) return false;
        }
        return helper(s1, s2, s3);
    }
};

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

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (k != m + n) return false;
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        
        vector<bool> map(n+1, false);
   
        map[0] = 1;
        for(int i = 1; i <=n; i++) 
            map[i] = map[i-1] && s2[i-1] == s3[i-1];
        
        for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               map[j]= (s3[i+j-1]==s1[i-1] && map[j]) ||(s3[i+j-1]==s2[j-1] && map[j-1]);
           }
        }
           
        return map[n];
    }
};