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
Post a Comment