Scramble String problem

Statement

We will be given two strings a, and b we have to check whether one string is scrambled version of other string or not.

Scrambled string:
let's string a = "great" and b = "rgeat"

then when make binary tree if string a
there are many way to partition a string
by dividing a into substrings one of the solution we get is

   gr|eat
   /    \
 g|r    e|at
 / \    /  \
g   r  e   a|t
           / \
          a   t 

now if we have to make scrambled version a
we can choose any of the non leaf node and swap its children nodes

ex: for the above if we swap childrens of non leaf node gr then we can get string "rgeat" which is scrambled version of "great"

like this we will be given two string we need to check if one is scrambled version of other

therefore we can say that b is scrambled version of a or a is scrambled version of b

---

Recursive Solution

for solving this we need divide both strings in two parts from same index

a = "great", b = "rgeat"

let's divide both string
a => gr | eat
b => rg | eat

let's first part of a be f(a) [f(a)="gr"] , second part of a = s(a) [s(a)="eat"]

first part of b be f(b) [f(b)="rg"] , second part of b = s(b) [s(b)="eat"]

for dividing strings in two parts we will loop as we have to check each possibilities

for above example we will check each possibilities ['|' is used for showing division]

• a = g|reat, b = r|geat
• a = gr|eat, b = rg|eat
• a = gre|at, b = rge|at
• a = grea|t, b = rgea|t

and then we need to check two conditions

1. if f(a) is scrambled version of s(b) && s(a) is scrambled version of f(b)
2. if f(a) is scrambled version of s(a) && s(a) is scrambled version of f(b)

if any one of the condition is satisfied then one string scrabbled version of other

also we will call same function recursively to check whether substring of string is scrambled or not

Note:

• if two strings are equal then they are scrambled version of each other
• if two strings are empty then also they are scrambled version of each other
• if length of both strings are not equal then strings are not scrambled

Pseudo Code:

bool is_scrambled(string a, string b){

    if(a==b) return true

    if(a.length != b.length) return false

    dividing strings using loop{
        if (is_scrambled(f(a), s(b)) and is_scrambled(s(a), f(b))){
            return true  //string b is scrambled version of a
        }
        if (is_scrambled(f(a), s(a)) and is_scrambled(s(b), f(b))){
            return true  //string b is scrambled version of a
        }
    }

    else return false
    
}

Example

a="great", b="rgeat"

for is_scramble(a, b) where a="great", b = "rgeat"

---

In first iteration

condition 1:

[ if (is_scrambled(f(a), s(b)) and is_scrambled(s(a), f(b))) ]

1] is_scrambled(f(a), s(a))

when f(a)="g", s(b) = "geat"
as length of both are not equal then both are not scrambled we will return false

2] is_scrambled(s(b), f(b))

when s(a)="reat", f(b) = "r"
as length of both are not equal then both are not scrambled return false

condition 1 will return false

condition 2:

[if (is_scrambled(f(a), s(a)) and is_scrambled(s(b), f(b)))]

1] is_scrambled(f(a), f(b))

when f(a)="g", f(b)="r"
as both strings are not equal and we can't divide both string further we will return false

2] is_scrambled(s(a), s(b))

when s(a)="reat", s(b)="geat"
as characters of both strings are not same this will return false in further recursion

therefore,

condition 2 will return false

both first and second condition are false then move further

---

In second iteration

f(a) = "gr", s(a) = "eat"

f(b) = "rg", s(b) = "eat"

condition 1:

[ if (is_scrambled(f(a), s(b)) and is_scrambled(s(a), f(b))) ]

1] is_scrambled(f(a), s(a))
as length of both f(a) and s(b) are not equal this will return false

2] is_scrambled(s(b), f(b))
also length of both s(a) and f(b) are not equal therefore return false

condition 1 will return false

condition 2:

[if (is_scrambled(f(a), s(a)) and is_scrambled(s(b), f(b)))]

1] is_scrambled(f(a), s(a))
as f(a) and f(b) can be further divided therefore this will called recursively

so,

f'(a)="g", s'(a)="r"

f'(b)="r", s'(b)="g"

f'(a) and s'(a) be the further division of f(a) and same for b

when we will check condition for this

1st condition:

as f'(a) and s'(b) are equal then return true

as s'(a) and f'(b) are equal then return true

therefore is_scrambled(f(a), s(a)) will return true

2] is_scrambled(s(a), s(b))

as both s(a) and s(b) are equal this will return true

condition 2 will return true

as condition is true then is_scrambled(a, b) will return true

hence, b="rgeat" is scrambled version of a="great"

---

Code

#include<bits/stdc++.h>
using namespace std;

bool scramble(string a, string b){
    if(a.compare(b) == 0) return true;
    if(a.length()!=b.length()) return false;
    int n = a.length();
    bool flag = false, c1, c2;

    for(int i=1; i<=n-1; i++){
        c1 = scramble(a.substr(0, i), b.substr(n-i, i));
        c2 = scramble(a.substr(i, n-i), b.substr(0, n-i));
        if(c1 and c2){
            flag = true; break;
        }
        c1 = scramble(a.substr(0, i), b.substr(0, i));
        c2 = scramble(a.substr(i, n-1), b.substr(i, n-1));
        if(c1 and c2){
            flag = true; break;
        }
    }
    return flag;
}

void solve(){
    string a, b; 
    cin>>a;
    cin>>b;
    cout<<scramble(a, b);
}

int main(){
    solve();
    return 0;
}

Input

great
rgeat

Output

1

---

Dynamic programming Solution

In this method we will just add dynamic programming to previous recursive solution
we will create map and store solution for each recursive call so that whenever same call will happen in future then we will just return that from map instead for running code
if solution is not present then we will execute code further
at last we will save result of execution in map

for map key will be string and value will be boolean

key = str1 + "," + str2
if str1="qwe", str2="rty"
key = "qwe,rty"

and value will store whether str1 and str2 are scrambled version of each other or not

whenever we are calling recursive function first we will check of solution for same function is present in our map for not

if yes then we will return result of that function

else we will perform operation and at last we will store result of that operation in map

---

Code

#include<bits/stdc++.h>
using namespace std;

bool scramble(string a, string b, map<string, bool> &dp){
    if(a.compare(b) == 0) return true;
    if(a.length()!=b.length()) return false;
    int n = a.length();
    bool flag = false, c1, c2;

    if(dp.find(a+","+b)!=dp.end()) return dp[a+","+b];

    for(int i=1; i<=n-1; i++){
        //  1st condition
        string temp = a.substr(0, i)+","+b.substr(n-i, i);
        if(dp.find(temp)!=dp.end()) c1=dp[temp];
        else c1 = scramble(a.substr(0, i), b.substr(n-i, i), dp);

        temp = a.substr(i, n-i) +","+ b.substr(0, n-i);
        if(dp.find(temp)!=dp.end()) c2=dp[temp];
        else c2 = scramble(a.substr(i, n-i), b.substr(0, n-i), dp);

        if(c1 and c2){
            flag = true; break;
        }

        //  2nd condition
        temp = a.substr(0, i) + "," + b.substr(0, i);
        if(dp.find(temp)!=dp.end()) c1=dp[temp];
        else c1 = scramble(a.substr(0, i), b.substr(0, i), dp);

        temp = a.substr(i, n-1)+","+b.substr(i, n-1);
        if(dp.find(temp)!=dp.end()) c2=dp[temp];
        else c2 = scramble(a.substr(i, n-1), b.substr(i, n-1), dp);

        if(c1 and c2){
            flag = true; break;
        }
    }
    dp[a+","+b]=flag;
    return flag;
}

void solve(){
    string a, b; 
    cin>>a;
    cin>>b;
    map<string, bool> dp;
    cout<<scramble(a, b, dp);
}

int main(){
    solve();
    return 0;
}

Input

great
rgeat

Output

1