LeetCode //C - 87. Scramble String

87. Scramble String

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.

Example 1:

Example 2:

Example 3:

Constraints:

s1.length == s2.length
1 <= s1.length <= 30
s1 and s2 consist of lowercase English letters.

From: LeetCode
Link: 87. Scramble String

Solution:

Ideas:

1. Recursive Definition: We want to define a function isScramble(s1, s2) that returns true if s2 can be a scrambled version of s1. This function will be implemented using a helper function checkScramble(s1, start1, s2, start2, len) which checks if the substring s1[start1:start1+len] can be transformed into the substring s2[start2:start2+len].

2. Memoization: To avoid recalculating the results for the same substrings over and over again (which leads to exponential time complexity), we use a memoization table memo[start1][start2][len]. This 3D array stores the results for all checked substrings:

start1 is the starting index in s1.
start2 is the starting index in s2.
len is the length of the substring being considered.
If memo[start1][start2][len] has been computed, it will return the result immediately, reducing redundant computations.

3. Base and Edge Cases:

If the two substrings are equal (s1[start1:start1+len] == s2[start2:start2+len]), they are trivially scramble strings of each other.
If the substrings have different character frequencies, they cannot be scramble strings of each other.

4. Recursive Splitting: For each possible way to split the substrings:

Without Swapping: First, check if the first part of s1 can be scrambled into the first part of s2 and the second part of s1 into the second part of s2.
With Swapping: Check if the first part of s1 can be scrambled into the second part of s2 (from the end) and the second part of s1 into the first part of s2.

5. Pruning with Character Count: Before trying to recursively split the strings, we check if the two substrings have the same character count. If not, we can immediately conclude that one cannot be scrambled into the other.

Code:

int memo[31][31][31];

// Helper function to check if two substrings have the same character counts
bool sameCharacterCount(char *s1, int start1, char *s2, int start2, int len) {
    int count[26] = {0};
    for (int i = 0; i < len; i++) {
        count[s1[start1 + i] - 'a']++;
        count[s2[start2 + i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }
    return true;
}

bool checkScramble(char *s1, int start1, char *s2, int start2, int len) {
    // Check memoized result first
    if (memo[start1][start2][len] != -1) {
        return memo[start1][start2][len];
    }
    
    // If the substrings are equal
    if (strncmp(s1 + start1, s2 + start2, len) == 0) {
        memo[start1][start2][len] = 1;
        return true;
    }

    // Ensure these substrings have the same character counts
    if (!sameCharacterCount(s1, start1, s2, start2, len)) {
        memo[start1][start2][len] = 0;
        return false;
    }

    // Try every possible split
    for (int i = 1; i < len; i++) {
        // Check the split without swap
        if (checkScramble(s1, start1, s2, start2, i) &&
            checkScramble(s1, start1 + i, s2, start2 + i, len - i)) {
            memo[start1][start2][len] = 1;
            return true;
        }
        // Check the split with swap
        if (checkScramble(s1, start1, s2, start2 + len - i, i) &&
            checkScramble(s1, start1 + i, s2, start2, len - i)) {
            memo[start1][start2][len] = 1;
            return true;
        }
    }

    memo[start1][start2][len] = 0;
    return false;
}

bool isScramble(char *s1, char *s2) {
    int len = strlen(s1);
    
    // Initialize memo array with -1 (uncomputed state)
    memset(memo, -1, sizeof(memo));
    
    return checkScramble(s1, 0, s2, 0, len);
}

Navigator_Z