Leetcode Problem 87 - Scramble String

 87. Scramble String

Hard, Dynamic Programming

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

1. If the length of the string is 1, stop.
2. 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.

 

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 and s2 consist of lowercase English letters.

To solve the Scramble String problem, we can use dynamic programming (DP) to efficiently check if s2 is a scrambled string of s1. The problem can be understood as a recursive process where we split the strings at different positions and recursively check for possible scrambled configurations.

Approach:

We can define a recursive relationship where:

1. If s1 and s2 are identical, we return true.
2. If s1 and s2 have different characters, we return false.
3. If s1 and s2 can be divided into two substrings, we need to check two conditions:
   • No Swap: The first part of s1 can match the first part of s2 and the second part of s1 matches the second part of s2.
   • With Swap: The first part of s1 matches the second part of s2 and the second part of s1 matches the first part of s2.

Dynamic Programming Approach:

We can use memoization to store the results of subproblems to avoid redundant calculations. Specifically, we use a 3D DP table dp[i][j][len] where:

• i and j represent the starting indices of the substrings in s1 and s2.
• len is the length of the substring.
• dp[i][j][len] = true if the substring s1[i..i+len-1] can be scrambled to form s2[j..j+len-1].

Code:

public class Solution {
    public bool IsScramble(string s1, string s2) {
        if (s1.Length != s2.Length) return false; // If lengths are different, return false
        
        // Initialize the DP array for memoization
        int n = s1.Length;
        bool[,,] dp = new bool[n, n, n + 1];
        
        // Base case: when the substring lengths are 1, we only need to check the characters
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j, 1] = s1[i] == s2[j];
            }
        }
        
        // Check for all possible lengths of the substrings from 2 to n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        // No Swap case: s1[i..i+k-1] and s1[i+k..i+len-1] match s2[j..j+k-1] and s2[j+k..j+len-1]
                        if (dp[i, j, k] && dp[i + k, j + k, len - k]) {
                            dp[i, j, len] = true;
                            break;
                        }
                        
                        // With Swap case: s1[i..i+k-1] and s1[i+k..i+len-1] match s2[j+len-k..j+len-1] and s2[j..j+k-1]
                        if (dp[i, j + len - k, k] && dp[i + k, j, len - k]) {
                            dp[i, j, len] = true;
                            break;
                        }
                    }
                }
            }
        }

        // Return whether the entire string can be scrambled from s1 to s2
        return dp[0, 0, n];
    }
}

Explanation:

1. Base Case:

   • If the substrings have a length of 1, we simply check if the characters at those positions are equal, i.e., s1[i] == s2[j].

2. Filling the DP Table:

   • For each possible substring length (len), starting from 2 up to the length of the string n, we check all possible starting indices i and j for s1 and s2.
   • For each combination of substrings of length len, we try both the "no swap" and "with swap" conditions:
     • No Swap: The first k characters of s1 should match the first k characters of s2, and the remaining characters should also match.
     • With Swap: The first k characters of s1 should match the last k characters of s2, and the remaining characters should also match.

3. Final Result:

   • The result of whether s1 can be scrambled to s2 is stored in dp[0, 0, n] where n is the length of the strings.

Time Complexity:

• Time Complexity: $O(n^4)$, where n is the length of the strings. This is because we have 3 loops:
  • len loop runs from 2 to n.
  • i and j loops both run from 0 to n - len.
  • The inner loop (k) runs up to len.
• Space Complexity: $O(n^3)$ for the 3D DP table.

Example Walkthrough:

For the input:

s1 = "great", s2 = "rgeat"

• The algorithm recursively checks whether s1 can be scrambled to form s2 using both possible cases (with or without swap).
• It iterates through all possible substring splits and applies the scramble check recursively, storing results in the DP table for optimization.
• Ultimately, it returns true because s2 is indeed a scrambled string of s1.

Edge Cases:

• If the strings are identical (e.g., s1 = "a", s2 = "a"), the result is true.
• If the strings have different characters, the result is false (e.g., s1 = "abc", s2 = "def").
• The solution handles all edge cases within the given constraints (1 <= s1.length <= 30).

This dynamic programming solution is efficient and avoids redundant calculations by using memoization, making it suitable for the given constraints.

Another approach for solving the Scramble String problem that also involves recursion with memoization. The key idea in this approach is to use a recursive check for scramble relationships and utilize caching (memoization) to store already computed results for substrings, which helps in avoiding redundant recalculations.

Approach: Recursive with Memoization

In this approach, we define a recursive function to check if a substring of s1 can be scrambled to form a corresponding substring of s2. The recursion works as follows:

1. Base Case: If the two strings are identical, they are trivially scrambled (return true).
2. Character Frequency Check: If the two strings have different character frequencies (i.e., the same characters in a different order), then s2 cannot be a scrambled version of s1, and we return false.
3. Recursive Step:
   • We recursively divide the strings into two parts at each possible position k and check:
     • No Swap Case: Whether the first k characters of s1 can scramble to the first k characters of s2, and the remaining part of s1 can scramble to the remaining part of s2.
     • Swap Case: Whether the first k characters of s1 can scramble to the last k characters of s2, and the remaining part of s1 can scramble to the first part of s2.
4. Memoization: Store the results of the recursive calls for each substring combination to avoid redundant calculations.

Code:

public class Solution {
    public bool IsScramble(string s1, string s2) {
        // Memoization dictionary to store the results of subproblems
        Dictionary<string, bool> memo = new Dictionary<string, bool>();
        
        // Helper function for recursion with memoization
        return IsScrambleHelper(s1, s2, memo);
    }
    
    private bool IsScrambleHelper(string s1, string s2, Dictionary<string, bool> memo) {
        // If the two strings are identical, no need to scramble
        if (s1 == s2) return true;
        
        // If the lengths of the strings are different, they can't be scrambled
        if (s1.Length != s2.Length) return false;
        
        // Check if the result is already computed and stored in memo
        string key = s1 + " " + s2;
        if (memo.ContainsKey(key)) return memo[key];
        
        // If the two strings have different character counts, return false
        if (!IsSameCharacterCount(s1, s2)) {
            memo[key] = false;
            return false;
        }
        
        int n = s1.Length;
        for (int i = 1; i < n; i++) {
            // Check for both swap and no swap cases
            if ((IsScrambleHelper(s1.Substring(0, i), s2.Substring(0, i), memo) && 
                 IsScrambleHelper(s1.Substring(i), s2.Substring(i), memo)) || 
                (IsScrambleHelper(s1.Substring(0, i), s2.Substring(n - i), memo) && 
                 IsScrambleHelper(s1.Substring(i), s2.Substring(0, n - i), memo))) {
                memo[key] = true;
                return true;
            }
        }
        
        // Store the result in memo for future use
        memo[key] = false;
        return false;
    }
    
    // Helper function to check if both strings have the same character count
    private bool IsSameCharacterCount(string s1, string s2) {
        int[] count = new int[26];
        for (int i = 0; i < s1.Length; i++) {
            count[s1[i] - 'a']++;
            count[s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }
}

Explanation:

1. Memoization: A dictionary memo is used to store previously computed results for pairs of strings (s1, s2). This prevents redundant recursive calls and optimizes performance.
2. Base Case: If s1 and s2 are the same string, return true. If their lengths differ, return false.
3. Character Frequency Check: Before diving into recursion, we check if s1 and s2 contain the same characters in the same frequency using the IsSameCharacterCount helper function. If they don't, return false.
4. Recursive Case: We recursively check for both the "no swap" and "swap" cases by splitting the strings at every possible position i. If any of the cases return true, we conclude that s1 can be scrambled to form s2.
5. Memoization Storage: If we find that a pair of substrings can't be scrambled to each other, we store the result false in the memo dictionary. If we find that they can, we store true.

Time Complexity:

• Time Complexity: $O(n^3)$, where n is the length of the string. This is because:
  • Each pair of substrings is checked and stored in the memo dictionary.
  • For each substring pair, we check all possible splits.
  • The recursive calls involve checking the same substring pairs multiple times, which is why memoization helps to avoid redundant work.
• Space Complexity: $O(n^3)$ for the memo dictionary and the recursion stack.

Example Walkthrough:

For input s1 = "great" and s2 = "rgeat", the function proceeds as follows:

1. The algorithm checks if s1 and s2 have the same character counts.
2. It then recursively splits both strings at each possible position and checks both swap and non-swap configurations.
3. The recursion will eventually find that s1 can be scrambled into s2, and return true.

Edge Cases:

• If s1 and s2 are already equal, the algorithm returns true without further recursion.
• If s1 and s2 have different character sets, the result will be false immediately.

This approach is effective, and with memoization, the solution avoids recalculating the same results multiple times, leading to better performance compared to the naive recursive approach.