0ms using recursion without dp


  • 0
    E

    Here is my idea:

    1. Our goal is to cut the "head" (same chars at the beginning) in s3 until it's empty. e.g.: when s3="aabcc", the first step is to cut off "aa", then band"cc".
    2. When we do this, we must make sure we have the same sub-string in s1, s2 and cut them off.

    count()is used to count the number of char same as s3[0], and then we do the analysis step by step. During each recursion, we must cut off the head in s3with the same char, so we always have s3.substr(numS3, s3.size() - numS3)when we call the next recursion.

    1. if (s1.size() + s2.size() != s3.size())return false;
      if (!s3.size())return true;
      These is obvious.
    2. if (numS1 + numS2 < numS3) return false;
      e.g.: s1="ab", s2="ab",s3="aaab";There is no enoughains1,s2to cut off in s3.
    3. if (numS1 + numS2 == numS3)
      woudourful, cut all of them.
    4. if (numS1 > numS3) or if (numS2 > numS3)
      e.g.: s1="aaa", s2="ab",s3="aabaa";, Whenaais cut off ins3, we have to cut twoawithins1,s2. It will be fail at the next step if we cutaains1. So we must cuts2first.
    5. At last, a normal recursion. Note that we have to choose cut all of the head ins1or ins2.

    It may be a little redundant. But I'm going to post here, because I think it is helpful to speed up when the head is long.
    It's still would possible to have the same case recursion and solve repeatedly. So it can be improved by employing dp.


    C++:

    class Solution {
    private:
    	//	count chars same as the first char
    	int count(string s, char first) {
    		unsigned int num = 0;
    		while (num < s.size() && s[num] == first)num++;
    		return num;
    	}
    public:
    	bool isInterleave(string s1, string s2, string s3) {
    		if (s1.size() + s2.size() != s3.size())return false;
    		if (!s3.size())return true;
    
    		int numS1 = count(s1, s3[0]);
    		int numS2 = count(s2, s3[0]);
    		int numS3 = count(s3, s3[0]);
    
    		//	special cases
    		if (numS1+numS2<numS3)	return false;
    		if (numS1 > numS3&&numS2 > numS3)	return false;
    		if (numS1 + numS2 == numS3)	return isInterleave(s1.substr(numS1,s1.size()-numS1),s2.substr(numS2,s2.size()-numS2),s3.substr(numS3,s3.size()-numS3));
    		if (numS1 == 0) return isInterleave(s1, s2.substr(numS3, s2.size() - numS3), s3.substr(numS3, s3.size() - numS3));
    		if (numS2 == 0) return isInterleave(s1.substr(numS3, s1.size() - numS3), s2, s3.substr(numS3, s3.size() - numS3));
    		if (numS1 > numS3) return isInterleave(s1.substr(numS3-numS2,s1.size()-(numS3 - numS2)), s2.substr(numS2,s2.size()-numS2), s3.substr(numS3,s3.size()-numS3));
    		if (numS2 > numS3) return isInterleave(s1.substr(numS1, s1.size() - numS1), s2.substr(numS3 - numS1, s2.size() - (numS3 - numS1)), s3.substr(numS3, s3.size() - numS3));
    
    		return isInterleave(s1.substr(numS3 - numS2, s1.size() - (numS3 - numS2)), s2.substr(numS2, s2.size() - numS2), s3.substr(numS3, s3.size() - numS3))
    			|| isInterleave(s1.substr(numS1, s1.size() - numS1), s2.substr(numS3 - numS1, s2.size() - (numS3 - numS1)), s3.substr(numS3, s3.size() - numS3));
    	}
    };
    

    I'm a beginner and looking forward for your advices*


  • 0
    E

    a little change

    class Solution {
    private:
    	
    	//	count chars same as the first one
    	int count(string s, int base, char first) {
    		unsigned int num = 0;
    		while (base + num < s.size() && s[base + num] == first)num++;
    		return num;
    	}
    	bool isInterleaveAux(string s1, unsigned int base1, string s2, unsigned int base2, string s3, unsigned int base3) {
    		if (base1 > s1.size() || base2 > s2.size())	return false;
    		if (base3==s3.size())	return true;
    
    		int numS1 = count(s1, base1, s3[base3]);
    		int numS2 = count(s2, base2, s3[base3]);
    		int numS3 = count(s3, base3, s3[base3]);
    
    		//	special cases
    		if (numS1 + numS2 < numS3)	return false;
    		if (numS1 > numS3&&numS2 > numS3)	return false;
    		//	cut s1&s2
    		if (numS1 + numS2 == numS3)	return isInterleaveAux(s1, base1 + numS1, s2, base2 + numS2, s3, base3 + numS3);
    
    		//	Note that now numS1+numS2>numS3
    		//	cut the one has
    		if (numS1 == 0) return isInterleaveAux(s1, base1, s2, base2 + numS3, s3, base3 + numS3);
    		if (numS2 == 0) return isInterleaveAux(s1, base1 + numS3, s2, base2, s3, base3 + numS3);
    		//	cut all the one less
    		if (numS1 > numS3) return isInterleaveAux(s1, base1 + numS3 - numS2, s2, base2 + numS2, s3, base3 + numS3);
    		if (numS2 > numS3) return isInterleaveAux(s1, base1 + numS1, s2, base2 + numS3 - numS1, s3, base3 + numS3);
    
    		//	cut all one of them
    		return isInterleaveAux(s1, base1 + numS3 - numS2, s2, base2 + numS2, s3, base3 + numS3)
    			|| isInterleaveAux(s1, base1 + numS1, s2, base2 + numS3 - numS1, s3, base3 + numS3);
    	}
    public:
    	bool isInterleave(string s1, string s2, string s3) {
    		if (s1.size() + s2.size() != s3.size())	return false;
    		return	isInterleaveAux(s1, 0, s2, 0, s3, 0);
    	}
    };
    

Log in to reply
 

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