How can I make my code efficient?


  • 0
    R
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            return isInterleave(s1, 0, s2, 0, s3,0);
        }
    private:
        bool isInterleave(string& s1, int i , string& s2, int j, string& s3, int k){
            if(Map.count(make_tuple(i,j,k))) return Map[make_tuple(i,j,k)];
            if(k==s3.size()){ // we have completed the s3
                return(i==s1.size() && j==s2.size()); // they both should be finished      
            }
            bool option1=((i<s1.size() && s1[i]==s3[k])&&isInterleave(s1,i+1,s2,j,s3,k+1));
            bool option2=((j<s2.size() && s2[j]==s3[k])&&isInterleave(s1,i,s2,j+1,s3,k+1)); 
        	return  Map[make_tuple(i,j,k)]=(option1 || option2); 
        }
        map<tuple<int,int,int>, bool> Map;
    };

  • 0
    L

    Convert this recursion version to iteration version could be more efficient and reduce space complexity to O(n), n is the length of shorter string between s1 and s2.


Log in to reply
 

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