Recursive and cache solution. (C++ 4ms)


  • 0
    H
    class Solution {
    unordered_map<int, bool> cache;
    
    int hashCode(int x, int y) {
        return x * 100007 + y;
    }
    public:
    bool isInterleave(string s1, string s2, string s3) {
        cache.clear();
        if (s1.length() + s2.length() != s3.length()) return false;
        return Core(s1, 0, s2, 0, s3);
    }
    
    bool Core(string& s1, int index1, string& s2, int index2, string& s3) {
        int hash = hashCode(index1, index2);
        if (cache.find(hash) == cache.end()) {
            int i = index1 + index2;
            const int length = s3.length();
            for (; i < length; i++) {
                if (index1 == s1.length() && index2 == s2.length()) {
                    break;
                } else if (index1 == s1.length()) {
                    if (s2[index2++] != s3[i]) break; 
                } else if (index2 == s2.length()) {
                    if (s1[index1++] != s3[i]) break; 
                } else if (s1[index1] != s2[index2]) {
                    if (s1[index1] == s3[i]) index1++;
                    else if (s2[index2] == s3[i]) index2++;
                    else break;
                } else {
                    if (s1[index1] != s3[i]) break;
                    if (Core(s1, index1+1, s2, index2, s3)) { cache[hash] = true; return true; }
                    if (Core(s1, index1, s2, index2+1, s3)) { cache[hash] = true; return true; }
                    break;
                }
            }
            if (i == length) cache[hash] = true;
            else cache[hash] = false;
        }
        return cache[hash];
    }
    

    };


Log in to reply
 

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