6. Check if a valid shuffle of two distinct strings

6. Check if a valid shuffle of two distinct strings


Problem link :- click here


package programs;

public class String__6
{

	/*
	 	Check if a string is a valid shuffle of two distinct strings.
	 		1xy2     is        a valid shuffle of         "xy"  and  "12"
	 		y12x     is not a valid shuffle of          "xy"  and "12"
	 		
	 	the order of each character in those strings should be maintained.
	 	
	 	 lets think we are creating the string with valid shuffle then while 
	 	 adding each character we have only two choices.
	 	 	
	 	 lets take an example        "xy"     "12"
	 	 1) we have to add either     'x'    or   '1'             add     'x'
	 	 2) we have to add either     'y'    or   '1'             add     '1'
	 	 3)                                          'y'     or   '2'            add     'y'
	 	 4) now we have only one choice         '2'           add     '2'
	 	 
	 	 NOW the valid shuffle string we created is       "x1y2"     
	 	 
	 	 we will check if same steps are followed, if not followed 
	 	 then it is not a valid shuffle
	*/
	
	static Boolean shuffleCheck(String s1, String s2, String result)
	{
		if( s1.length() + s2.length()    !=     result.length() )
			return false;
		
		//take iterators for each string
		int i = 0;            //   s1
		int j = 0;            //   s2
		int k = 0;           //   result
		
		//similar to merge in merge-sort
		while( i<s1.length()   &&    j<s2.length() )
		{
			if(  result.charAt(k)  ==  s1.charAt(i)  )
				i++;
			else if(  result.charAt(k)  ==  s2.charAt(j)  )
				j++;
			
			//incrementing in the above conditions because steps are followed
			//steps not followed
			else
				return false;
			
			k++;
		}
		
		return true;
	}
	
	public static void main(String[] args)
	{
		String s1 = "abcd";
		String s2 = "1234";
		String res = "a12b3cd4";
		
		Boolean ans = shuffleCheck(s1, s2, res);
		if(ans)
			System.out.println("Valid Shuffle");
		else
			System.out.println("Not valid shuffle");
	}

}

Time complexity :- O(n)
Space complexity :- O(1)

Comments

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree