Scramble String
Problem Description
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 s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
Examples
Example 1
Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
Example 2
Input: s1 = "abcde", s2 = "caebd"
Output: false
Example 3
Input: s1 = "a", s2 = "a"
Output: true
Constraints
s1.length == s2.length1 <= s1.length <= 30s1 and s2consist of lowercase English letters.
Approach
We will first check the base cases i.e., if the two strings are equal or not or if they are of different sizes. Then, we will create a key for the current problem by concatenating the two strings and storing it in a dictionary to avoid repeated computations. We will iterate over all possible splits of the current string and check whether we need to swap the left and right substrings or not. We will then make recursive calls on these two substrings and return true if any of the calls return true.
Solution Code
C++
class Solution {
private:
int dp[40][40][40];
bool solve(string &s1,string &s2,int l1,int l2,int len){
if(len == 0){
return dp[l1][l2][len]=true;
}
if(dp[l1][l2][len]!=-1){
return dp[l1][l2][len];
}
for(int i=l1,j=l2;i<=len+l1;i++,j++){
if(i==l1+len){
return dp[l1][l2][len]=true;
}
if(s1[i]!=s2[j]){
break;
}
}
vector<int>v(26,0);
for(int i=l1,j=l2;i<len+l1;i++,j++){
v[s1[i]-'a']++;
v[s2[j]-'a']--;
}
for(auto x:v){
if(x) return dp[l1][l2][len]=false;
}
for(int i=1;i<len;i++){
if(solve(s1,s2,l1,l2,i) && solve(s1,s2,l1+i,l2+i,len - i)){
return dp[l1][l2][len]=true;
}
if(solve(s1,s2,l1+i,l2,len-i)&&solve(s1,s2,l1,l2+(len-i),i)){
return dp[l1][l2][len]=true;
}
}
return dp[l1][l2][len]=false;
}
public:
bool isScramble(string s1, string s2) {
memset(dp, -1 ,sizeof dp);
return solve(s1,s2,0,0,s1.size());
}
};
Java
class Solution {
// to store previously computed substrings
Map<String, Boolean> map = new HashMap<>();
public boolean isScramble(String s1, String s2) {
int n = s1.length();
// check if the two strings are equal
if (s1.equals(s2)) {
return true;
}
// initialize frequency arrays for s1, s2, and current substring
int[] a = new int[26], b = new int[26], c = new int[26];
// check if the current substring has already been computed
if (map.containsKey(s1 + s2)) {
return map.get(s1 + s2);
}
// check all possible splits of the two strings
for (int i = 1; i <= n - 1; i++) {
int j = n - i;
// update frequency arrays for s1, s2, and current substring
a[s1.charAt(i - 1) - 'a']++;
b[s2.charAt(i - 1) - 'a']++;
c[s2.charAt(j) - 'a']++;
// check if the current substring has the same characters
if (Arrays.equals(a, b) && isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
// if the substrings are scrambled versions of each other, return true
map.put(s1 + s2, true);
return true;
}
// check if the current substring and its complement have the same characters
if (Arrays.equals(a, c) && isScramble(s1.substring(0, i), s2.substring(j)) && isScramble(s1.substring(i), s2.substring(0, j))) {
// if the substrings are scrambled versions of each other, return true
map.put(s1 + s2, true);
return true;
}
}
// if none of the splits result in scrambled versions, return false
map.put(s1 + s2, false);
return false;
}
}
Python
class Solution:
# dictionary to store previously computed substrings
map = {}
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
# check if the two strings are equal
if s1 == s2:
return True
# initialize frequency lists for s1, s2, and current substring
a, b, c = [0] * 26, [0] * 26, [0] * 26
# check if the current substring has already been computed
if (s1 + s2) in self.map:
return self.map[s1 + s2]
# check all possible splits of the two strings
for i in range(1, n):
j = n - i
# update frequency lists for s1, s2, and current substring
a[ord(s1[i - 1]) - ord('a')] += 1
b[ord(s2[i - 1]) - ord('a')] += 1
c[ord(s2[j]) - ord('a')] += 1
# check if the current substring has the same characters
if a == b and self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
# if the substrings are scrambled versions of each other, return True
self.map[s1 + s2] = True
return True
# check if the current substring and its complement have the same characters
if a == c and self.isScramble(s1[:i], s2[j:]) and self.isScramble(s1[i:], s2[:j]):
# if the substrings are scrambled versions of each other, return True
self.map[s1 + s2] = True
return True
# if none of the splits result in scrambled versions, return False
self.map[s1 + s2] = False
return False
Conclusion
-
Time complexity:
O(n^4) -
Space complexity:
O(n^2)