Scramble String

Difficulty Level Medium
Frequently asked in Amazon Fanatics Samsung
Divide and Conquer Dynamic Programming String TreeViews 4642

Problem Statement

“Scramble String” problem states that you are given two strings. Check if the second string is a scrambled string of first one or not?

Explanation

Let string s = “great”

Representation of s as binary tree by recursively dividing it into two non-empty sub-strings.

Scramble String

This string can be scrambled by choosing any non leaf node and swapping it’s children.

Scramble String

Therefore “rgeat” is a scrambled string of original string i.e. “great”.

Example

s1 = "great"

s2 = "rgeat"
Yes

Explanation: As shown above in the images, we can see scrambling “great” results in “great”. And thus the result is Yes.

s1 = "abcde"

s2 = "caebd"
No

 

Algorithm for Scramble String Problem

1. Initialize the two string variables s1 and s2 of the same size.
2. Create a function to check is the second string is the scrambled string of first string which accepts two string variables as it's a parameter.
3. Check if the first string is equal to the second string, return true.
4. After that, sort the first string using the inbuilt sort function.
5. Similarly, sort the second string using the inbuilt sort function.
6. Check again if the first string is not equal to the second string, return false.
7. Else create a variable scramble of the boolean type and initialize it as false.
8. After that, traverse from 0 to the length of the string and make a recursive call to the function itself for all the possible index combinations of the first string and the second string and store the result of the recursive calls in the boolean variable scramble.
9. Finally, check If the value of the boolean variable scramble is equal to the true then print "Yes".
10. Else if the value of the boolean variable scramble is equal to the false then print "No".

for solving this problem, first of all, we try to check a few things. The first thing which we check is whether both the strings are equal or not. By equal, here we mean that characters at all the indices of the string are the same or not. If they are the same, then we are sure that the second string is scrambled string of the other. But if they are not equal we check if after sorting the strings. They are equal or not.

After sorting if they are equal then there is a possibility that second input might be a scrambled string of the first. But if they are not equal then we are sure that we won’t be able to find any solution such that the second input is scrambled string of the first one. Now after all these operations, we check if the second input is scrambled or not by recursively calling the function.

Code

C++ Program to check scramble string

#include <iostream> 
#include <algorithm>
#include <string>
using namespace std;

bool isAnagram( string s1, string s2 ){
    sort( s1.begin(), s1.end() );
    sort( s2.begin(), s2.end() );
    if( s1 != s2 )
        return false;
    else 
        return true;
}

bool isScramble(string s1, string s2){
    if( s1 == s2 )
        return true;

    if( !isAnagram( s1, s2 ) )
        return false;
            
    bool scramble = false;
    int length = s1.length();
    for( int i = 1; i < length; i++ ){
        scramble = scramble || 
                   ( isScramble( s1.substr( 0, i ), s2.substr( 0, i ) ) &&
                   isScramble( s1.substr( i, length - i ), s2.substr( i, length - i ) ) )||
                   ( isScramble( s1.substr( 0, i ), s2.substr( length - i, i ) ) &&
                   isScramble( s1.substr( i, length - i ), s2.substr( 0, length - i ) ) );
    }
    return scramble;
}

int main(){
  string s1 = "great";
  string s2 = "rgeat";
  if(isScramble(s1,s2)){
      cout<<"Yes";
  }
  else{
      cout<<"No";
  }
  return 0;
}
Yes

Java Program to check scramble string

import java.util.*;

class Scramble{
    
    static boolean isScramble(String s1, String s2){
       
        if(s1.length()!=s2.length())
            return false;
     
        if(s1.length()==0 || s1.equals(s2))
            return true;
     
        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();
        
        Arrays.sort(a1);
        Arrays.sort(a2);
        
        if(!new String(a1).equals(new String(a2))){
            return false;
        }
     
        for(int i=1; i<s1.length(); i++){
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i, s1.length());
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i, s2.length());
            String s23 = s2.substring(0, s2.length()-i);
            String s24 = s2.substring(s2.length()-i, s2.length());
     
            if(isScramble(s11, s21) && isScramble(s12, s22))
                return true;
            if(isScramble(s11, s24) && isScramble(s12, s23))
                return true;    
        }    
     
        return false;
    }

  public static void main (String[] args){
    String s1 = "great";
    String s2 = "rgeat";
    if(isScramble(s1,s2)){
        System.out.println("Yes");
    }
    else{
        System.out.println("No");
    }
  }
}

Yes

Complexity Analysis

Time Complexity

O(2^n) where n is the number of characters in the first string or the second string.

Space Complexity

O(2^n) because we used 2^n space for characters of the first and the second string in the program.

Translate »