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


  • 0
    X
    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();
        }
    };

Log in to reply
 

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