Clean c++ dp and dfs solution


  • 0

    DP:

    bool isInterleave(string s1, string s2, string s3) {
        int size1 = s1.size(), size2 = s2.size(), size3 = s3.size();
        if (size1 + size2 != size3)
            return false;
        vector<int> match(size1 + 1);
        match[0] = true;
        int start = 0;
        while (start < size1 && s1[start] == s3[start])
            match[++start] = true;
        for (int i = 0; i < size2; i++) {
            match[0] &= s2[i] == s3[i];
            for (int j = 0; j < size1; j++) {
                char t = s3[i + j + 1];
                match[j + 1] = (s2[i] == t && match[j + 1]) || (s1[j] == t && match[j]);
            }
        }
        return match[size1];
    }
    

    DFS:

    bool isInterleave(string s1, string s2, string s3) {
        unordered_map<string, int> match;
        return isInterleave(s1, 0, s2, 0, s3, 0, match);
    }
    
    bool isInterleave(string &s1, int index1, string &s2, int index2, string &s3, int index3, unordered_map<string, int> &match) {
        string current = to_string(index1) + '+' + to_string(index2);
        if (match.find(current) != match.end())
            return match[current];
        int size1 = s1.size(), size2 = s2.size(), size3 = s3.size();
        int result;
        if (index3 == size3) {
            if (index1 == size1 && index2 == size2)
                result = true;
            else
                result = false;
        } else {
            if (index1 < size1 && s1[index1] == s3[index3]
                && isInterleave(s1, index1 + 1, s2, index2, s3, index3 + 1, match))
                result = true;
            else if (index2 < size2 && s2[index2] == s3[index3]
                && isInterleave(s1, index1, s2, index2 + 1, s3, index3 + 1, match))
                result = true;
            else
                result = false;
        }
        match[current] = result;
        return result;
    }
    

  • 0
    E

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.