
Problem Statement
Scrambling a string involves dividing it into non-empty substrings and randomly deciding whether to swap these substrings or not, then recursively applying the same operation. Given two strings, s1
and s2
, both of the same length, we want to determine if s2
can be obtained by scrambling s1
through any sequence of operations. If such a scrambling operation sequence can lead from s1
to s2
, return true
; 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.length
1 <= s1.length <= 30
s1
ands2
consist of lowercase English letters.
Approach and Intuition
The process of determining if one string is a scrambled version of another can be broken down as follows:
Base Case Handling:
- If both strings are identical, then clearly
s2
is a scrambled version ofs1
. - If the sorted versions of the strings do not match, they can't be scrambles of each other since scrambling doesn't alter the letter count but only their order.
- If both strings are identical, then clearly
Recursive Checks:
- For each possible split of
s1
, check if one split is a scramble of the corresponding split ins2
(both without swapping and with swapping the splits). - This check is recursive since after splitting, each of the sub-parts can themselves be scrambled further.
- For each possible split of
Caching for Efficiency:
- Given the potential overlaps in subproblem calculations, employing memoization (caching results of subproblems) can significantly speed up the checking.
From the examples:
Example 1:
s1 = "great"
,s2 = "rgeat"
.s1
can be split into ("gr", "eat"), and then "gr" can be scrambled to "rg", while "eat" remains unchanged.- As seen, there exists a valid series of operations to turn "great" into "rgeat", so we would return
true
.
Example 2:
s1 = "abcde"
,s2 = "caebd"
.- No matter how you split and attempt to scramble “abcde”, you can’t arrive at “caebd”. The check for matching sorted versions of
s1
ands2
already shows they are different. Thus,false
is returned.
- No matter how you split and attempt to scramble “abcde”, you can’t arrive at “caebd”. The check for matching sorted versions of
Example 3: Trivial case with
s1 = "a"
,s2 = "a"
, where both strings being identical, directly returnstrue
.
The constraints of the problem ensure argument equality in length and limit the possible operations with a maximum length of 30, making the recursive approach feasible within these bounds. Also, all characters are lowercase English letters, restricting the character set and simplifying sorting and comparison operations.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
bool canScramble(string str1, string str2) {
int len = str1.length();
vector<vector<vector<int>>> memo(len + 1, vector<vector<int>>(len, vector<int>(len)));
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
memo[1][i][j] = str1[i] == str2[j];
}
}
for (int l = 2; l <= len; l++) {
for (int i = 0; i <= len - l; i++) {
for (int j = 0; j <= len - l; j++) {
for (int k = 1; k < l; k++) {
const auto& firstHalf = memo[k][i];
const auto& secondHalf = memo[l - k][i + k];
memo[l][i][j] |= firstHalf[j] && secondHalf[j + k];
memo[l][i][j] |=
firstHalf[j + l - k] && secondHalf[j];
}
}
}
}
return memo[len][0][0];
}
};
This solution tackles the problem of determining if one string can be transformed into another by a series of scramble operations. In C++, the implementation uses dynamic programming to efficiently decide if the second string is a scrambled version of the first.
- A 3D vector
memo
is initialized to store the boolean results of subproblems. Each elementmemo[l][i][j]
represents whether a substring ofstr1
starting at indexi
with lengthl
can be transformed into a substring ofstr2
starting at indexj
of the same length. - The base case is set immediately for substrings of length 1, comparing characters at corresponding positions in
str1
andstr2
. - For substrings longer than 1, the solution combines results from smaller substrings. This involves checking both scenarios where a string might be directly scrambled or split and swapped.
- Continuous updates to
memo
occur by iterating over the substring lengthl
, the starting indicesi
andj
, and split positionsk
within each lengthl
. - Ultimately, the result is found in
memo[len][0][0]
wherelen
is the length ofstr1
, indicating whether the entirestr1
can be scrambled intostr2
.
Make sure to understand the memoization structure and how the indices and loops interact since correct indexing is crucial for this solution to work. Furthermore, consider effective debugging and testing with different string lengths and contents to fully assess the implementation's accuracy and efficiency.
class Solution {
public boolean canScramble(String str1, String str2) {
int len = str1.length();
boolean scrambled[][][] = new boolean[len + 1][len][len];
for (int index1 = 0; index1 < len; index1++) {
for (int index2 = 0; index2 < len; index2++) {
scrambled[1][index1][index2] = str1.charAt(index1) == str2.charAt(index2);
}
}
for (int l = 2; l <= len; l++) {
for (int i = 0; i < len + 1 - l; i++) {
for (int j = 0; j < len + 1 - l; j++) {
for (int splitPoint = 1; splitPoint < l; splitPoint++) {
boolean[] scramblePart1 = scrambled[splitPoint][i];
boolean[] scramblePart2 = scrambled[l - splitPoint][i + splitPoint];
scrambled[l][i][j] |= scramblePart1[j] && scramblePart2[j + splitPoint];
scrambled[l][i][j] |=
scramblePart1[j + l - splitPoint] && scramblePart2[j];
}
}
}
}
return scrambled[len][0][0];
}
}
In the provided Java solution for determining if one string is a scramble of another, the core approach involves dynamic programming to efficiently break down and solve the problem.
- The function
canScramble
accepts two stringsstr1
andstr2
as input. - A 3-dimensional boolean array
scrambled
is declared to store intermediate results, which spans across possible string lengths, and the start indices of substrings in bothstr1
andstr2
. - Initialization of
scrambled
involves settingtrue
when characters directly match betweenstr1
andstr2
at each position for substrings of length 1. - The solution then considers substrings of increasing length. For each length
l
, and starting indicesi
instr1
andj
instr2
, it checks if there exists a split pointsplitPoint
that validates the scramble condition based on previously computed results. - Scrambling conditions for both possible segment divisions (keeping the order and swapping) are checked using logical OR (
|=
), updating thescrambled
array. - Finally, the result for the full length of the strings starting from index
0
in both strings indicates ifstr2
is a scramble ofstr1
.
This method leverages dynamic programming's overlapping subproblem property to effectively manage the complexity and avoid redundant calculations. By storing intermediate results and referring back to them, it optimizes both time and space compared to a straightforward recursive approach. The end result is determined by checking the top-level entry in the scrambled
array for the full string.
bool scrambledStrings(char* str1, char* str2) {
int len = strlen(str1);
bool scramble_dp[len + 1][len][len];
memset(scramble_dp, false, sizeof(scramble_dp));
for (int idx = 0; idx < len; idx++) {
for (int jdx = 0; jdx < len; jdx++) {
scramble_dp[1][idx][jdx] = str1[idx] == str2[jdx];
}
}
for (int segment = 2; segment <= len; segment++) {
for (int idx = 0; idx <= len - segment; idx++) {
for (int jdx = 0; jdx <= len - segment; jdx++) {
for (int k = 1; k < segment; k++) {
bool* left = scramble_dp[k][idx];
bool* right = scramble_dp[segment - k][idx + k];
scramble_dp[segment][idx][jdx] =
scramble_dp[segment][idx][jdx] || (left[jdx] && right[jdx + k]);
scramble_dp[segment][idx][jdx] = scramble_dp[segment][idx][jdx] ||
(left[jdx + segment - k] && right[jdx]);
}
}
}
}
return scramble_dp[len][0][0];
}
This solution implements a function to determine if one string is a scrambled version of another using dynamic programming. The function scrambledStrings
takes two character pointers str1
and str2
as inputs and returns a boolean value indicating whether str2
is a scrambled string of str1
.
Process Summary
The function begins by determining the length of
str1
and initializing a 3D boolean arrayscramble_dp
to keep track of subproblem solutions. The dimensions of this array depend on the length of the string, with each entryscramble_dp[segment][idx][jdx]
indicating whether the segment ofstr1
starting atidx
and the segment ofstr2
starting atjdx
with lengthsegment
are scrambles of each other.Initially, for segments of length 1, the function sets
scramble_dp[1][idx][jdx]
totrue
if the characters atstr1[idx]
andstr2[jdx]
are the same.For longer segments, the function looks at all possible splits of the segment into two parts. For each possible split, it checks two conditions using the already computed values in
scramble_dp
:- Whether one part of
str1
is a scramble of one part ofstr2
and the other part ofstr1
is a scramble of the other part ofstr2
. - Whether one part of
str1
is a scramble of the reversed part ofstr2
and vice versa.
- Whether one part of
This is done in a nested loop structure where the outer loop iterates over all possible segment lengths (from 2 to
len
), and the inner two loops iterate over possible start indices for these segments in both strings.The final outcome, whether the entire
str1
is a scrambled version ofstr2
, is stored inscramble_dp[len][0][0]
.
The algorithm efficiently solves the problem by building solutions for small segments and using them to solve for larger segments, ensuring that all combinations of segments are considered.
var scrambleCheck = function (str1, str2) {
const len = str1.length;
let memo = new Array(len + 1)
.fill(0)
.map(() => new Array(len).fill(0).map(() => new Array(len).fill(false)));
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
memo[1][i][j] = str1.charAt(i) == str2.charAt(j);
}
}
for (let segmentLength = 2; segmentLength <= len; segmentLength++) {
for (let i = 0; i < len + 1 - segmentLength; i++) {
for (let j = 0; j < len + 1 - segmentLength; j++) {
for (let partLen = 1; partLen < segmentLength; partLen++) {
const part1 = memo[partLen][i];
const part2 = memo[segmentLength - partLen][i + partLen];
memo[segmentLength][i][j] |= part1[j] && part2[j + partLen];
memo[segmentLength][i][j] |= part1[j + segmentLength - partLen] && part2[j];
}
}
}
}
return memo[len][0][0];
};
This article guides you through the JavaScript implementation of a function that checks if two strings are scramble strings of each other.
The function scrambleCheck
is defined to take two strings, str1
and str2
, as inputs and returns a boolean indicating whether the two strings can be transformed into one another by a series of scrambles. Scrambling involves breaking a string into two non-empty parts and swapping them.
- First, the function calculates the length of
str1
and uses this length to initialize a 3D arraymemo
. This array stores boolean values representing the scramble status of different segments of the strings. - The base case is set up where single characters in
str1
are checked against characters instr2
. If they match, the corresponding memo value is set to true. - The function then considers segment lengths from 2 up to the length of the strings. For each segment length, all possible starting indices for the segments in
str1
andstr2
are evaluated. - For every possible partition of the segment (
partLen
), the function checks two conditions:- Scrambling without crossing: where the two parts before and after the partition in
str1
directly match the segments instr2
- Scrambling with crossing: where the first part of
str1
matches the second part ofstr2
and vice versa
- Scrambling without crossing: where the two parts before and after the partition in
- These checks update the
memo
array for larger segments based on the results of smaller segments. - Finally, the function returns the value from the memo array that indicates whether the entire
str1
can be scrambled to matchstr2
.
Using dynamic programming, this solution efficiently determines the scramble status between the two strings by building solutions for smaller segments and combining them to address larger segments. This avoids redundant calculations seen in naive recursive approaches, leading to improved performance.
class Solution:
def checkScramble(self, str1: str, str2: str) -> bool:
limit = len(str1)
memo = [
[[False for x in range(limit)] for y in range(limit)] for z in range(limit + 1)
]
for x in range(limit):
for y in range(limit):
memo[1][x][y] = str1[x] == str2[y]
for sz in range(2, limit + 1):
for x in range(limit + 1 - sz):
for y in range(limit + 1 - sz):
for split in range(1, sz):
subMemo1 = memo[split][x]
subMemo2 = memo[sz - split][x + split]
memo[sz][x][y] |= subMemo1[y] and subMemo2[y + split]
memo[sz][x][y] |= (
subMemo1[y + sz - split] and subMemo2[y]
)
return memo[limit][0][0]
The provided code defines a function to determine if one string is a scramble of another. Scrambling here involves potentially splitting the string into two at any point, and then swapping these two parts, recursively.
To solve this problem, the function checkScramble
uses a dynamic programming approach. The key elements in the implementation are:
memo
: A 3D list that stores boolean values, initialized to track the scramble status for substrings of various lengths and starting positions.- Initialization: Set each element
memo[1][x][y]
toTrue
if the characters at positionx
instr1
andy
instr2
are the same. This addresses the base case where substrings are of length 1. - Nested loops are used to build up the solution for strings from size 2 up to the full length of
str1
. For each size (sz
), starting indices (x
) instr1
andstr2
(y
) are considered. - For each possible substring size and starting index, consider all possible splits. This is facilitated by a further nested loop over
split
, indicating where the split occurs. - Conditions evaluated in these loops check whether making a particular split and potentially swapping leads to both parts matching corresponding parts in the other string.
- The computed results of shorter substrings are reused to determine the result for larger substrings, culminating in whether the total strings
str1
andstr2
can be considered scrambles of each other, stored inmemo[limit][0][0]
.
This method provides a clear and efficient way to recursively decide if two strings can be transformed into one another by this specific scrambling process. By leveraging dynamic programming, the function efficiently subdivides and conquers the problem, using previously calculated results to speed up the solution. This method is quite effective for large strings as it avoids redundant recalculations found in plain recursive approaches.
No comments yet.