Scramble String In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

The “Scramble String” problem is a classical recursive problem that deals with determining if one string is a scrambled version of another.

Problem Statement

Given two strings, s1 and s2, check if s2 is a scrambled version of s1.

A scrambled string of s1 can be obtained by recursively applying the following operations:

  1. Split the string into two non-empty substrings.
  2. Swap the two substrings.
  3. Optionally, repeat the process on each substring.

Examples

Example 1:

Input:
s1 = "great", s2 = "rgeat"
Output:
true
Explanation:

  • Split "great" into "gr" and "eat".
  • Swap "gr" and "eat" to get "eatgr".
  • Scramble "gr" to "rg" and "eat" remains unchanged.

Example 2:

Input:
s1 = "abcde", s2 = "caebd"
Output:
false

Example 3:

Input:
s1 = "a", s2 = "a"
Output:
true

Approach and Algorithm

1. Recursive Approach

We recursively check all possible ways to split the strings and validate if either:

  • The left part of s1 is a scramble of the left part of s2 and the right parts are scrambles of each other.
  • The left part of s1 is a scramble of the right part of s2 and the right part of s1 is a scramble of the left part of s2.

2. Dynamic Programming (DP)

We use a 3D DP table to store results for substrings of s1 and s2.

Complexity

  1. Time Complexity: O(N^4), where N is the length of the strings.
  2. Space Complexity: O(N^3), for the DP table.

Code Implementation

C:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isScrambleUtil(char *s1, char *s2, int n) {
    if (strncmp(s1, s2, n) == 0) return true;
    if (n == 1) return s1[0] == s2[0];

    int freq[26] = {0};
    for (int i = 0; i < n; i++) {
        freq[s1[i] - 'a']++;
        freq[s2[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] != 0) return false;
    }

    for (int i = 1; i < n; i++) {
        if (isScrambleUtil(s1, s2, i) && isScrambleUtil(s1 + i, s2 + i, n - i)) return true;
        if (isScrambleUtil(s1, s2 + n - i, i) && isScrambleUtil(s1 + i, s2, n - i)) return true;
    }

    return false;
}

bool isScramble(char *s1, char *s2) {
    int n = strlen(s1);
    if (n != strlen(s2)) return false;
    return isScrambleUtil(s1, s2, n);
}

int main() {
    char s1[] = "great";
    char s2[] = "rgeat";
    printf("Is Scramble: %s\n", isScramble(s1, s2) ? "true" : "false");
    return 0;
}

C++:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, bool> memo;

bool isScrambleUtil(string s1, string s2) {
    if (s1 == s2) return true;
    if (s1.size() != s2.size()) return false;

    string key = s1 + "#" + s2;
    if (memo.find(key) != memo.end()) return memo[key];

    int n = s1.size();
    int freq[26] = {0};

    for (int i = 0; i < n; i++) {
        freq[s1[i] - 'a']++;
        freq[s2[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] != 0) return memo[key] = false;
    }

    for (int i = 1; i < n; i++) {
        if (isScrambleUtil(s1.substr(0, i), s2.substr(0, i)) &&
            isScrambleUtil(s1.substr(i), s2.substr(i))) {
            return memo[key] = true;
        }
        if (isScrambleUtil(s1.substr(0, i), s2.substr(n - i)) &&
            isScrambleUtil(s1.substr(i), s2.substr(0, n - i))) {
            return memo[key] = true;
        }
    }
    return memo[key] = false;
}

bool isScramble(string s1, string s2) {
    memo.clear();
    return isScrambleUtil(s1, s2);
}

int main() {
    string s1 = "great", s2 = "rgeat";
    cout << "Is Scramble: " << (isScramble(s1, s2) ? "true" : "false") << endl;
    return 0;
}

Java:

import java.util.HashMap;
import java.util.Map;

public class ScrambleString {
    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();
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            freq[s1.charAt(i) - 'a']++;
            freq[s2.charAt(i) - 'a']--;
        }
        for (int f : freq) {
            if (f != 0) return memo.put(key, false);
        }

        for (int i = 1; i < n; i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                isScramble(s1.substring(i), s2.substring(i))) {
                return memo.put(key, true);
            }
            if (isScramble(s1.substring(0, i), s2.substring(n - i)) &&
                isScramble(s1.substring(i), s2.substring(0, n - i))) {
                return memo.put(key, true);
            }
        }
        return memo.put(key, false);
    }

    public static void main(String[] args) {
        String s1 = "great", s2 = "rgeat";
        System.out.println("Is Scramble: " + isScramble(s1, s2));
    }
}

Python:

def isScramble(s1, s2):
    if s1 == s2:
        return True
    if sorted(s1) != sorted(s2):
        return False

    n = len(s1)
    for i in range(1, n):
        if (isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:])) or \
           (isScramble(s1[:i], s2[-i:]) and isScramble(s1[i:], s2[:-i])):
            return True
    return False

# Example Usage
s1 = "great"
s2 = "rgeat"
print("Is Scramble:", isScramble(s1, s2))

JavaScript:

function isScramble(s1, s2) {
    if (s1 === s2) return true;
    if (s1.split("").sort().join("") !== s2.split("").sort().join("")) return false;

    let n = s1.length;
    for (let i = 1; i < n; i++) {
        if (
            (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                isScramble(s1.substring(i), s2.substring(i))) ||
            (isScramble(s1.substring(0, i), s2.substring(n - i)) &&
                isScramble(s1.substring(i), s2.substring(0, n - i)))
        ) {
            return true;
        }
    }
    return false;
}

// Example Usage
let s1 = "great";
let s2 = "rgeat";
console.log("Is Scramble:", isScramble(s1, s2));

C# 

using System;
using System.Collections.Generic;

public class ScrambleString
{
    // Memoization dictionary to store previously computed results
    static Dictionary<string, bool> memo = new Dictionary<string, bool>();

    // Helper function to check if one string is a scramble of the other
    public static bool IsScramble(string s1, string s2)
    {
        // If both strings are equal, no need to check further
        if (s1 == s2)
            return true;

        // If the lengths of the strings are not the same, return false immediately
        if (s1.Length != s2.Length)
            return false;

        // Create a key for memoization from the two strings
        string key = s1 + "#" + s2;

        // If the result for this pair of strings is already computed, return it
        if (memo.ContainsKey(key))
            return memo[key];

        // Check if both strings contain the same characters in the same frequency
        int[] freq = new int[26];
        for (int i = 0; i < s1.Length; i++)
        {
            freq[s1[i] - 'a']++;
            freq[s2[i] - 'a']--;
        }

        // If the frequencies don't match, they cannot be scrambles
        foreach (var f in freq)
        {
            if (f != 0)
            {
                memo[key] = false; // Store the result in memoization dictionary
                return false;
            }
        }

        // Now, check for the two conditions of scrambled strings:
        for (int i = 1; i < s1.Length; i++)
        {
            // Case 1: No swapping of substrings
            if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) &&
                IsScramble(s1.Substring(i), s2.Substring(i)))
            {
                memo[key] = true; // Memoize the result
                return true;
            }

            // Case 2: Swapping of substrings
            if (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length - i)) &&
                IsScramble(s1.Substring(i), s2.Substring(0, s2.Length - i)))
            {
                memo[key] = true; // Memoize the result
                return true;
            }
        }

        // If no valid scramble was found, memoize and return false
        memo[key] = false;
        return false;
    }

    // Main function to test the scramble string function
    public static void Main()
    {
        string s1 = "great";
        string s2 = "rgeat";

        Console.WriteLine("Is Scramble: " + IsScramble(s1, s2));  // Output: true

        s1 = "abcde";
        s2 = "caebd";
        
        Console.WriteLine("Is Scramble: " + IsScramble(s1, s2));  // Output: false
    }
}