# Interesting variation with a couple of pre-optimizations, C++, O(M*N) worst-case, linear space, 4ms

• ``````class Solution {
void getFreqs(const string& s, vector<size_t>& q)
{
for(auto& c : s)
{
++q[c];
}
}
public:
bool isInterleave(string s1, string s2, string s3) {
// A couple of quick sanity checks to filter out some a priori false cases in constant or linear time
if(s3.size() != s1.size() + s2.size())
{
return false;
}

// each character in s3 should have the frequency equal to the sum of frequencies of the same character in s1 and s2
vector<size_t> q(256), q1(256), q2(256);
getFreqs(s3, q);
getFreqs(s1, q1);
getFreqs(s2, q2);
for(auto k = 0; k < q.size(); ++k)
{
if(q[k] != q1[k] + q2[k])
{
return false;
}
}

// now the main algorithm, O(s1.size()*s2.size()) worst-case time complexity, O(min(s1.size(), s2.size())) space complexity; best-case is O(s1.size() + s2.size())
size_t i1 = 0, i2 = 0, i = 0;
stack<tuple<size_t, size_t, size_t>> states;
set<tuple<size_t, size_t, size_t>> reg;
while(i < s3.size())
{
if(!reg.insert(make_tuple(i, i1, i2)).second) // duplicate state reached and it has already been checked at this point, so try out anything else we've stored
{
tuple<size_t, size_t, size_t> t;
while(!states.empty())
{
t = states.top();
if(reg.find(t) != reg.end())
{
states.pop();
}
else
{
break;
}
}
if(!states.empty())
{
states.pop();
i = get<0>(t);
i1 = get<1>(t);
i2 = get<2>(t);
}
else
{
return false;
}
}
if(i1 < s1.size() && s3[i] == s1[i1])
{
if(i2 < s2.size() && s3[i] == s2[i2])
{
states.push(make_tuple(i + 1, i1, i2 + 1));
}
++i;
++i1;
}
else if(i2 < s2.size() && s3[i] == s2[i2])
{
++i;
++i2;
}
}
return i1 == s1.size() && i2 == s2.size();
}
};``````

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