My Accepted Java Recursive Solution for interleaving string


  • 22
    J
    public class Solution {
      	private static Set<Integer> visited; // The combination of i1, i2 has been visited and return false
    	public static boolean isInterleave(String s1, String s2, String s3) {
    		if(s3.length() != s1.length() + s2.length())
    			return false;
    		visited = new HashSet<Integer>();
    		return isInterleave(s1, 0, s2, 0, s3, 0);
    	}
    	
    	private static boolean isInterleave(String s1, int i1, String s2, int i2, String s3, int i3)
    	{	
    		int hash = i1 * s3.length() + i2;
    		if(visited.contains(hash))
    			return false;
    		
    		if(i1 == s1.length())
    			return s2.substring(i2).equals(s3.substring(i3));
    		if(i2 == s2.length())
    			return s1.substring(i1).equals(s3.substring(i3));
    		
    		if(s3.charAt(i3) == s1.charAt(i1) && isInterleave(s1, i1+1, s2, i2, s3, i3+1) ||
    		   s3.charAt(i3) == s2.charAt(i2) && isInterleave(s1, i1, s2, i2+1, s3, i3+1))
    			return true;
    		
    		visited.add(hash);
    		return false;
    	}
    }
    

    The private method isInterleave is the recursive method. it takes additional i1, i2, i3 as the start indexes of s1, s2, s3, so it solves the substring of s1, s2, s3 with those start indexes.

    The recursion starting condition is i1, i2, i3 are set to 0, means it solves the whole string.

    in each recursion, it will just check the first character in s3 with s2 and s1, if it equals s1, it will increase i3 and i1 to solve remain, if remain return true, this recursion will also return true. Same logic for s2.

    The end condition is when remain of either s1 or s2 is empty, then just compare remain of s3 with remain of s1 or s2, if they are equal, it will return true.

    A pure recursive solution will cause time limit exceed. We can optimize it by caching the false visited solutions in the visited set. That will short circuit many repeated search path.


  • 1
    W

    A pure recursive solution will cause time limit exceed. We can optimize it by caching the false visited solutions in the visited set. That will short circuit many repeated search path.

    。。。 i cannot understand how it works.


  • 0
    W

    I think the "hash = i1 * s3.length() + i2;" didn't have a exact meaning, it is just a symbol that i1 and i2 have worked already, it can be replaced by something as "i1 + i2*100"
    it can be accepted


  • 0
    N

    You can further optimize the solution by maintaining the indices of working combinations as well. i.e. if a combination of i1, i2 works, you should put it in another hash which should be checked at the beginning of isInterleave along with the visited hash.


  • 1
    I

    Caching visited solutions is actually a DP method. I think instead of only recording the false solutions, you can use a hashmap to record both true and false solutions


  • 1
    K

    I think the calculation of 'hash' is unnecessary, it can be replaced with an array 'dp[s1.length()][s2.length()]', they both need O(s1.length()*s2.length()) space, but the array doesn't need to calculate hash.


  • 3

    @kimixuchen Agree with you! You inspired me when I try to figure out how to encode and save into Set. Here is my DFS solution now. Thanks~

        private boolean[][] visited;
        
        public boolean isInterleave(String s1, String s2, String s3) {
            if (visited == null) visited = new boolean[s1.length() + 1][s2.length() + 1];
            if (s3.isEmpty()) return s1.isEmpty() && s2.isEmpty();
            if (visited[s1.length()][s2.length()]) return false; // must be false!
            
            if (!s1.isEmpty() && s1.charAt(0) == s3.charAt(0) 
                && isInterleave(s1.substring(1), s2, s3.substring(1))) return true;
            if (!s2.isEmpty() && s2.charAt(0) == s3.charAt(0)
                && isInterleave(s1, s2.substring(1), s3.substring(1))) return true;
            visited[s1.length()][s2.length()] = true;
            return false;
        }
    

  • 0
    C

    @notsameer @ibmzzjn
    There is no need to store true Paths.
    Let me explain.
    We are using "Or" condition in If statement here to return true.
    i.e

    if(recurse(FirstPath) || recurse(SecondPath)){
         return true;
    }
    

    Suppose recurse(FirstPath) returns true, then we will have

    if( true || recurse(recurse(SecondPath)) 
    

    we won't recurse the second path because we already got If condition as True.

    if we get

    (false || recurse(SecondPath)) 
    

    we will have to recurse the second path also and check if this return true or false. Here Storing False Conditions while recursing First path helps.

    Note:-
    If you are not using If condition while recursing, i.e if your code is as Folls:-

    Boolean b1 = false;
    Boolean b2 = false;
    if( s3.charAt(i3) == s1.charAt(i1) )
                b1= isInterleave(s1, i1+1, s2, i2, s3, i3+1);
    if( s3.charAt(i3) == s2.charAt(i2) )
               b2= isInterleave(s1, i1, s2, i2+1, s3, i3+1)
    
    if(b1  || b2 ){
        return true;  
    }
    else{
          return false    
    }
    
    

    In the above code it is important to store both True and False Paths.

    Hope this Helps.


  • 0
    C

    @wolong
    Go through this example:-

    S1=aab
    S2=aac
    S3=aacaab.


Log in to reply
 

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