C++ 4ms solution straight forward with memorization

  • 1

    very concise and straight forward, so it should be very easy to understand

    the trick is to convert index result to string and store result in a set to save some time

    class Solution {
        bool isInterleave(string s1, string s2, string s3) 
            if(s1.length()+s2.length()!=s3.length()) return false;
            return help(s1,0,s2,0,s3,0,result);
        bool help(string & s1, int i1, string & s2, int i2, string & s3, int i3, unordered_set<string>& result )
            if(i3==s3.length()) return true;
            string str = to_string(i1)+"_"+to_string(i2)+"_"+to_string(i3);
            if(result.find(str)!=result.end()) return false;
            if(i1<s1.length() && s1[i1]==s3[i3] && help(s1,i1+1,s2,i2,s3,i3+1,result)) return true;
            if(i2<s2.length() && s2[i2]==s3[i3] && help(s1,i1,s2,i2+1,s3,i3+1,result)) return true;
            return false;

  • 0

    Thank you.
    Very smart method to optimize!!!

    This line is really smart!
    string str = to_string(i1)+"_"+to_string(i2)+"_"+to_string(i3);

Log in to reply

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