Leetcode 87. Scramble String
Problem description
Given two strings of the same length, we are to determine if the second string (s2
) is a scrambled version of the first string (s1
). A string is said to be scrambled if it can be represented as a binary tree by partitioning it to two non-empty substrings recursively and at any step, we may choose any non-leaf node and swap its two children.
Problem Explanation
For example, take the string great
. We can represent it as follows:
1great
/
gr eat
/ \ /
g r e at
/
a t
We can scramble this by swapping the children of the node gr
:
1rgeat
/
rg eat
/ \ /
r g e at
/
a t
By the above operation, we can say that great
is a scrambled string of rgeat
. Similarly, we can swap the children of nodes eat
and at
to get a scrambled string rgtae
. As such we can say that great
is a scrambled string of rgtae
.
Problem Approach
Using a dynamic programming approach, we verify that for every possible division of s1
and s2
if it fits into one of the following scenarios:
s1
ands2
are the same.- For some
i
, the firsti
letters ins1
is a scramble of the firsti
letters ins2
and the rest is a scramble of the rest. - For some
i
, the firsti
letters ins1
is a scramble of the lasti
letters ins2
and the rest is a scramble of the rest.
The function isScramble
checks if the input strings s1
and s2
are scrambled strings of each other. The function uses memoization to avoid repetitive computation. If s1
and s2
are the same string, the function returns true
. If s1
and s2
are anagrams of each other but not the same string, then the function checks for possible divide points where the left and right substrings are scrambled strings of each other. The function checks this by recursively calling isScramble
for the left and right substrings of s1
and s2
.
Here's the pseudo code for the solution:
1
2
3function isScramble(s1: string, s2: string) {
4
5 if s1 is equal to s2 return true
6
7 if s1 is not an anagram of s2 return false
8
9 for each index i from 1 to string length - 1 {
10 if isScramble(left part of s1, left part of s2) and
11 isScramble(right part of s1, right part of s2) return true
12 if isScramble(left part of s1, right part of s2) and
13 isScramble(right part of s1, left part of s2) return true
14 }
15
16 return false
17}
Python Solution
1 2python 3class Solution: 4 def isScramble(self, s1: str, s2: str) -> bool: 5 if s1 == s2: 6 return True 7 if sorted(s1) != sorted(s2): 8 return False 9 length = len(s1) 10 for i in range(1, length): 11 if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]): 12 return True 13 if self.isScramble(s1[:i], s2[length-i:]) and self.isScramble(s1[i:], s2[:length-i]): 14 return True 15 return False
This python solution relies on the built-in python function sorted
to check if the two strings are anagrams of each other. It also uses python's slicing operations to divide the strings into left and right parts. You will notice the recursive calls to isScramble
to check the left and right parts of the strings.
Java Solution
1
2java
3class Solution {
4 public boolean isScramble(String s1, String s2) {
5 if (s1.equals(s2)) {
6 return true;
7 }
8 int[] letters = new int[26];
9 for (int i = 0; i < s1.length(); i++) {
10 letters[s1.charAt(i) - 'a']++;
11 letters[s2.charAt(i) - 'a']--;
12 }
13 for (int i = 0; i < 26; i++) {
14 if (letters[i] != 0) {
15 return false;
16 }
17 }
18 for (int i = 1; i < s1.length(); i++) {
19 if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
20 isScramble(s1.substring(i), s2.substring(i))) {
21 return true;
22 }
23 if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) &&
24 isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {
25 return true;
26 }
27 }
28 return false;
29 }
30}
This Java solution uses character counts to check if the two strings are anagrams of each other. It also uses Java's substring function to divide the strings into left and right parts. Like the Python solution, it recursively calls isScramble
to check the left and right parts of the strings.
JavaScript Solution
1
2javascript
3var isScramble = function(s1, s2) {
4 if (s1 === s2) return true;
5 if (s1.split('').sort().join('') !== s2.split('').sort().join('')) return false;
6
7 for(let i = 1; i < s1.length; i++) {
8 if(isScramble(s1.slice(0, i), s2.slice(0, i)) &&
9 isScramble(s1.slice(i), s2.slice(i))) {
10 return true;
11 }
12 if(isScramble(s1.slice(0, i), s2.slice(s2.length - i)) &&
13 isScramble(s1.slice(i), s2.slice(0, s2.length - i))) {
14 return true;
15 }
16 }
17 return false;
18};
This JavaScript solution converts the strings to arrays using the split function, sorts the arrays, and then compares them to see if they are anagrams. It also uses the slice function to divide the strings into left and right parts, and uses recursion to check if the left and right parts are scrambled strings of each other.
C++ Solution
1
2cpp
3class Solution {
4public:
5 bool isScramble(string s1, string s2) {
6 if (s1 == s2)
7 return true;
8 int l = s1.size();
9 int count[26] = {0};
10 for (int i = 0; i < l; i++) {
11 count[s1[i]-'a']++;
12 count[s2[i]-'a']--;
13 }
14 for (int i = 0; i < 26; i++)
15 if (count[i]!=0)
16 return false;
17 for(int i = 1; i <= l-1; i++) {
18 if(isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
19 return true;
20 // swap
21 if(isScramble(s1.substr(0,i), s2.substr(l-i)) && isScramble(s1.substr(i), s2.substr(0, l-i)))
22 return true;
23 }
24 return false;
25 }
26};
This C++ solution is implementing the same logic as the Java solution, it uses character counts to check if the two strings are anagrams of each other and the substr function to divide the strings into left and right parts. It also recursively calls isScramble to check the left and right parts of the strings.
C# Solution
1
2csharp
3public class Solution {
4 public bool IsScramble(string s1, string s2) {
5 if (s1 == s2) return true;
6 int[] letters = new int[26];
7 for (int i = 0; i < s1.Length; i++) {
8 letters[s1[i] - 'a']++;
9 letters[s2[i] - 'a']--;
10 }
11 for (int i = 0; i < 26; i++) {
12 if (letters[i] != 0) {
13 return false;
14 }
15 }
16 for (int i = 1; i < s1.Length; i++) {
17 if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) {
18 return true;
19 }
20 if (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length - i)) && IsScramble(s1.Substring(i), s2.Substring(0, s2.Length - i))) {
21 return true;
22 }
23 }
24 return false;
25 }
26}
In the C# implementation, like in the Java and C++ solutions, we are using character counts and substring division, followed by recursive calls, to achieve the solution. The only notable difference is the usage of C# specific syntax and conventions. Overall, solving the scrambled string problem with Python, Java, JavaScript, C++ and C# demonstrates the broad application of these programming concepts. The problem approach using dynamic programming is key in determining whether the second string is a scrambled version of the first string. The important things to achieve are the checks to confirm whether the two strings are anagrams of each other and the use of recursive function calls. Here's a simple breakdown of the problem solving process:
- Check to see if the input strings are equal. If they are, return
true
. - Check to see if the input strings are anagrams of each other. If they are not, return
false
. - Use a loop to check for possible divide points in the strings.
- Use the divide points to create two substrings from each input string.
- Recursively call the function using the substrings as new input strings.
- Continue until all possibilities have been checked.
In conclusion, even though the solution is implemented in different languages, the concept and logic remain the same. The differences are mostly in the syntax and specific language features such as using split
and join
in JavaScript or slice
in Python, Java's substring method, C#'s usage of conventions and syntax, and C++ constructs.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.