Problem Statement: Scramble String
Given two strings s1 and s2, return true if s2 is a scrambled string of s1. A string is scrambled if we can divide the string into two non-empty substrings and recursively swap them (or not) to obtain the target string.
Example 1:
Input:
s1 = "great", s2 = "rgeat"
Output:
true
Explanation: We can divide “great” into two substrings “gr” and “eat”, and swap them to get “rgeat”.
Example 2:
Input:
s1 = "abcde", s2 = "caebd"
Output:
false
Approach
We can solve this problem using Dynamic Programming (DP). The idea is to recursively check whether one string can be transformed into another by recursively swapping substrings.
Approach:
- Base Case: If
s1 == s2, then they are trivially scrambled. - Recursive Case:
- For each partition of
s1ands2, check if one part ofs1can be scrambled into one part ofs2(direct or swapped). - Use dynamic programming (memoization) to store intermediate results and avoid redundant computations.
- For each partition of
Time Complexity:
- Time Complexity: O(n^4), where
nis the length of the strings. This arises due to the number of possible substrings (O(n^2)) and recursive calls at each step. - Space Complexity: O(n^3) due to memoization storage.
C Code Implementation
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX 1000
bool dp[MAX][MAX][MAX]; // Memoization table
// Check if s1[0...len-1] and s2[0...len-1] are scrambled strings
bool isScramble(char* s1, char* s2, int len) {
if (strcmp(s1, s2) == 0) return true;
if (len <= 1) return false;
int index = len * 26; // Store position for memoization
if (dp[index][s1[0] - 'a'][s2[0] - 'a']) return true;
for (int i = 1; i < len; i++) {
if ((isScramble(s1, s2, i) && isScramble(s1 + i, s2 + i, len - i)) ||
(isScramble(s1, s2 + len - i, i) && isScramble(s1 + i, s2, len - i))) {
return true;
}
}
dp[index][s1[0] - 'a'][s2[0] - 'a'] = false;
return false;
}
int main() {
char s1[] = "great";
char s2[] = "rgeat";
if (isScramble(s1, s2, strlen(s1))) {
printf("True\n");
} else {
printf("False\n");
}
return 0;
}
C++ Code Implementation
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string, bool> memo;
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
if (s1.length() != s2.length()) return false;
string key = s1 + "_" + s2;
if (memo.count(key)) return memo[key];
int n = s1.length();
for (int i = 1; i < n; i++) {
// Case 1: Don't swap
if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i), s2.substr(i))) {
memo[key] = true;
return true;
}
// Case 2: Swap
if (isScramble(s1.substr(0, i), s2.substr(n - i)) &&
isScramble(s1.substr(i), s2.substr(0, n - i))) {
memo[key] = true;
return true;
}
}
memo[key] = false;
return false;
}
int main() {
string s1 = "great";
string s2 = "rgeat";
if (isScramble(s1, s2)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
}
Java Code Implementation
javaCopy codeimport java.util.HashMap;
import java.util.Map;
public class ScrambleString {
private static Map<String, Boolean> memo = new HashMap<>();
public static boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
if (s1.length() != s2.length()) return false;
String key = s1 + "_" + s2;
if (memo.containsKey(key)) return memo.get(key);
int n = s1.length();
for (int i = 1; i < n; i++) {
// Case 1: Don't swap
if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
isScramble(s1.substring(i), s2.substring(i))) {
memo.put(key, true);
return true;
}
// Case 2: Swap
if (isScramble(s1.substring(0, i), s2.substring(n - i)) &&
isScramble(s1.substring(i), s2.substring(0, n - i))) {
memo.put(key, true);
return true;
}
}
memo.put(key, false);
return false;
}
public static void main(String[] args) {
String s1 = "great";
String s2 = "rgeat";
if (isScramble(s1, s2)) {
System.out.println("True");
} else {
System.out.println("False");
}
}
}
Python Code Implementation
def isScramble(s1, s2, memo={}):
if s1 == s2:
return True
if len(s1) != len(s2):
return False
if (s1, s2) in memo:
return memo[(s1, s2)]
n = len(s1)
for i in range(1, n):
# Case 1: Don't swap
if isScramble(s1[:i], s2[:i], memo) and isScramble(s1[i:], s2[i:], memo):
memo[(s1, s2)] = True
return True
# Case 2: Swap
if isScramble(s1[:i], s2[-i:], memo) and isScramble(s1[i:], s2[:-i], memo):
memo[(s1, s2)] = True
return True
memo[(s1, s2)] = False
return False
# Example usage
s1 = "great"
s2 = "rgeat"
print(isScramble(s1, s2)) # Output: True
C# Code Implementation
using System;
using System.Collections.Generic;
public class ScrambleString
{
private static Dictionary<string, bool> memo = new Dictionary<string, bool>();
public static bool IsScramble(string s1, string s2)
{
if (s1 == s2) return true;
if (s1.Length != s2.Length) return false;
string key = s1 + "_" + s2;
if (memo.ContainsKey(key)) return memo[key];
int n = s1.Length;
for (int i = 1; i < n; i++)
{
// Case 1: Don't swap
if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) &&
IsScramble(s1.Substring(i), s2.Substring(i)))
{
memo[key] = true;
return true;
}
// Case 2: Swap
if (IsScramble(s1.Substring(0, i), s2.Substring(n - i)) &&
IsScramble(s1.Substring(i), s2.Substring(0, n - i)))
{
memo[key] = true;
return true;
}
}
memo[key] = false;
return false;
}
public static void Main()
{
string s1 = "great";
string s2 = "rgeat";
if (IsScramble(s1, s2))
{
Console.WriteLine("True");
}
else
{
Console.WriteLine("False");
}
}
}
JavaScript Code Implementation
const isScramble = (s1, s2, memo = {}) => {
if (s1 === s2) return true;
if (s1.length !== s2.length) return false;
const key = s1 + "_" + s2;
if (memo[key] !== undefined) return memo[key];
const n = s1.length;
for (let i = 1; i < n; i++) {
// Case 1: Don't swap
if (isScramble(s1.slice(0, i), s2.slice(0, i), memo) &&
isScramble(s1.slice(i), s2.slice(i), memo)) {
memo[key] = true;
return true;
}
// Case 2: Swap
if (isScramble(s1.slice(0, i), s2.slice(n - i), memo) &&
isScramble(s1.slice(i), s2.slice(0, n - i), memo)) {
memo[key] = true;
return true;
}
}
memo[key] = false;
return false;
};
// Example usage
const s1 = "great";
const s2 = "rgeat";
console.log(isScramble(s1, s2)); // Output: true
Conclusion
In all implementations, the core idea is to check recursively if a string can be scrambled into another string by splitting and possibly swapping substrings. Memoization is used to avoid redundant calculations and optimize the performance. The solution is implemented in C, C++, Java, Python, C#, and JavaScript to demonstrate the approach in multiple programming languages.