C++ 4ms solution straight forward with memorization


  • 1
    B

    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 {
    public:
        bool isInterleave(string s1, string s2, string s3) 
        {
            if(s1.length()+s2.length()!=s3.length()) return false;
            unordered_set<string>result;
            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;
            result.insert(str);
            return false;
        }
    };

  • 0
    L

    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.