Sponsored
Sponsored
This approach uses recursion to explore all possible valid splits and checks if either of the permutations exist. To avoid re-computation, use a dictionary to memoize already computed results for specific substrings.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.
1#include <string.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int memo[31][31][31];
6
7bool scrambleUtil(const char* s1, const char* s2, int i1, int i2, int length) {
8 if (strncmp(s1 + i1, s2 + i2, length) == 0) {
9 return true;
10 }
11 if (memo[i1][i2][length] != -1) {
12 return memo[i1][i2][length];
13 }
14 for (int i = 1; i < length; i++) {
15 if ((scrambleUtil(s1, s2, i1, i2, i) && scrambleUtil(s1, s2, i1 + i, i2 + i, length - i)) ||
16 (scrambleUtil(s1, s2, i1, i2 + length - i, i) && scrambleUtil(s1, s2, i1 + i, i2, length - i))) {
17 memo[i1][i2][length] = 1;
18 return true;
19 }
20 }
21 memo[i1][i2][length] = 0;
22 return false;
23}
24
25bool isScramble(char* s1, char* s2) {
26 int n = strlen(s1);
27 if (n != strlen(s2)) {
28 return false;
29 }
30 memset(memo, -1, sizeof(memo));
31 return scrambleUtil(s1, s2, 0, 0, n);
32}This solution uses a recursive method with memoization to solve the scramble string problem. The base condition checks if the two given substrings are equal. If the memoization array has previously computed the solution for the given problem, it returns that result, which avoids re-computation. The recursive call considers both swapping and not swapping the substrings when partitioning.
This approach is based on dynamic programming. We set up a 3D table where table[i][j][k] holds true if s1's substring starting at index i with length k is a scrambled string of s2's substring starting at index j.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.
1#include
In this C solution, we use a 3D boolean DP array dp with indices [i][j][k] indicating whether a substring starting at index i in s1 and a substring starting at index j in s2 of length k can be scrambles of each other. We fill this array iteratively, considering the divisions of the k-length substring into parts.