Scramble String-Coding question asked by Microsoft, Google, Salesforce, Meta

Problem Statement:

You are given an integer ’N’ two strings ‘s’ and ‘t’ each having size = ’N’. You can scramble the string ‘s’ to obtain string “t’ using the following operations:

We can scramble a string s to get a string t using the following algorithm:

If the length of the string is 1, stop.

If the length of the string is > 1, do the following:

Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.

Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.

Apply step 1 recursively on each of the two substrings x and y.

Given two strings s and t of the same length, return true if t is a scrambled string of s, otherwise, return false.

Input Format:

Two strings s and t.

Output Format:

Boolean value.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Sample Input 3:

Sample Output 3:

Explanation:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

We say that “rgtae” is a scrambled string of “great”.

Approach 1(Recursive):

Recursion of the string lengths do not equal or the characters are mismatch (use map), we can return false. Since each part can be scrambled, we need recursion to check scramble of left part and right part. As we swap the text, the match for left could also happen on the right side, we need to check the match between left and right as well

Time complexity O(2^n)

Space complexity O(n) due to recursion stack

Code of approach 1:

Approach 2(Dynamic):

We create three dimensional array, dp[][][], where dp[i][j][k] indicate the scrambleof length i and j-th character from s1 and kth character from s2. We need to check every possible breaking point from 1 to i — 1 using a variable b. Left part match left part, and right part match right part, so we check match from j and k with length b, and match from j + b and k + b with length i — b. Left part match right part, and right part match left part, so we check match from j and k + i — b with length b, and match from j + b and k for length i — b

Time complexity O(n⁴)

Space complexity O(n³)

Code for approach 2:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store