🚀

End of Year Sale: Use Coupon Code END2025 to Get Extra 25% Off.

11DAYS
:
05HOURS
:
27MINUTES
:
50SECONDS

Leetcode Problem 87. Scramble String

87. Scramble String

Leetcode Solutions

Dynamic Programming Approach for Scramble String

  1. Initialize a 3D boolean array dp with dimensions [n+1][n][n], where n is the length of the input strings.
  2. Set the base case in dp: for i from 0 to n-1, and for j from 0 to n-1, set dp[1][i][j] to true if s1[i] == s2[j], otherwise false.
  3. Iterate over the lengths of the substrings from 2 to n.
  4. For each length, iterate over all possible starting indices i for s1 and j for s2.
  5. For each pair of starting indices, iterate over all possible splits newLength from 1 to length - 1.
  6. Check both cases for each split: without swapping and with swapping.
  7. If any split satisfies the scrambled string condition, set dp[length][i][j] to true.
  8. Return the value of dp[n][0][0] as the final result.
UML Thumbnail

Recursive Approach with Memoization for Scramble String

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...