Leetcode 97 Solution

This article provides solution to leetcode question 97 (interleaving-string)
Categories:
Tags:
Access this page by simply typing in "lcs 97" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/interleaving-string

Solution

class Solution {
    map<tuple<int, int, int>, bool> cache;

public:
    bool isInterleave(const string& s1, const string& s2, const string& s3, int i1, int i2, int i3)
    {
        auto key = make_tuple(i1, i2, i3);

        if (cache.find(key) != cache.end())
            return cache[key];

        if (i3 == s3.size())
            return cache[key] = true;

        if (i1 != s1.size() && s3[i3] == s1[i1] && isInterleave(s1, s2, s3, i1 + 1, i2, i3 + 1))
            return cache[key] = true;

        if (i2 != s2.size() && s3[i3] == s2[i2] && isInterleave(s1, s2, s3, i1, i2 + 1, i3 + 1))
            return cache[key] = true;

        return cache[key] = false;
    }

    bool isInterleave(string s1, string s2, string s3)
    {
        if (s3.size() != s1.size() + s2.size())
            return false;

        return isInterleave(s1, s2, s3, 0, 0, 0);
    }
};