How can I make my code efficient?

  • 0
    class Solution {
        bool isInterleave(string s1, string s2, string s3) {
            return isInterleave(s1, 0, s2, 0, s3,0);
        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

    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.