interleaving_string.cc

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (!s1.size() && !s2.size() && !s3.size()) {
            return true;
        } else if (s1.size() > 0 && s2.size() > 0 && s3.size() > 0) {
            vector<vector<vector<int>>> mmap(s1.size(), vector<vector<int>>(s2.size(), vector<int>(s3.size(), -1)));
            return isInterleave(s1, s1.size() - 1, s2, s2.size() - 1, s3, s3.size() - 1, mmap);
        } else {
            return false;
        }
    }
    
    bool isInterleave(string &s1, int l1, string &s2, int l2, string &s3, int l3, vector<vector<vector<int>>> &mmap) {
        if (l1 < 0 && l2 < 0 && l3 < 0) {
            return true;
        } else if (l1 >= 0 && l2 >= 0 && l3 >=0 ) {
            if (mmap[l1][l2][l3] != -1) {
                return mmap[l1][l2][l3];
            }
            int temp;
            if (s1[l1] == s3[l3] && s2[l2] != s3[l3]) {
                temp = isInterleave(s1, l1 - 1, s2, l2, s3, l3 - 1, mmap);
            } else if (s1[l1] == s3[l3] && s2[l2] == s3[l3]) {
                temp = isInterleave(s1, l1 - 1, s2, l2, s3, l3 - 1, mmap) || isInterleave(s1, l1, s2, l2 - 1, s3, l3 - 1, mmap);
            } else if (s2[l2] == s3[l3] && s1[l1] != s3[l3]) {
                temp = isInterleave(s1, l1, s2, l2 - 1, s3, l3 - 1, mmap);
            } else {
                return false;
            }
            mmap[l1][l2][l3] = temp;
            return temp;
        } else {
            return false;
        }
    }
};