87. Scramble String
String, DP, Review ·Problem Statement
link: https://leetcode.com/problems/scramble-string/ https://leetcode.cn/problems/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:
Input: s1 = "great", s2 = "rgeat"
Output: true
Input: s1 = "abcde", s2 = "caebd"
Output: false
Input: s1 = "a", s2 = "a"
Output: true
Solution Approach
The problem is tackled using a recursive divide-and-conquer method, enhanced with dynamic programming to cache results and avoid repetitive calculations.
Algorithm
- Initial Verification: Compare the sorted characters of s1 and s2 for a quick mismatch identification.
- Recursive Substring Evaluation: For every possible split of the strings, examine both the original and swapped substring combinations, determining if they can be scrambled forms of each other.
- Memoization: Utilize a dynamic programming dictionary to store and retrieve previously calculated results for substring pairs, optimizing the performance.
Implement
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
dp = {}
def scramble(s1, s2):
key = (s1, s2) if s1 < s2 else (s2, s1)
if key in dp:
return dp[key]
if sorted(s1) != sorted(s2):
dp[key] = False
return False
if len(s1) == 1:
dp[key] = True
return True
for i in range(1, len(s1)):
if scramble(s1[:i], s2[:i]) and scramble(s1[i:], s2[i:]) or scramble(s1[:i],s2[-i:]) and scramble(s1[i:], s2[:-i]):
dp[key] = True
return True
dp[key] = False
return False
return scramble(s1, s2)