What is the time complexity of solving the Scramble String problem?

The time complexity is O(n^4) due to the memoization technique and the recursive nature of the problem.

How does dynamic programming help in solving Scramble String?

Dynamic programming helps by storing intermediate results of string scrambles, allowing you to avoid redundant calculations and speeding up the solution process.

What is the main challenge when solving Scramble String?

The main challenge is efficiently managing the recursive calls while checking both swap and non-swap scenarios, which requires careful use of memoization.

Can the Scramble String problem be solved without dynamic programming?

It is possible, but without dynamic programming, the solution would be inefficient, leading to redundant calculations and higher time complexity.

What are some common mistakes when solving Scramble String?

Common mistakes include failing to properly handle recursive cases, neglecting memoization, and missing edge cases like identical or unswappable strings.

#87

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：如果字符串的长度为 1 ，算法停止如果字符串的长度 > 1 ，执行下述步骤：在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。随机决定是…

字符串动态规划

题目描述

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
- 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
- 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
- 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"
输出：false

示例 3：

输入：s1 = "a", s2 = "a"
输出：true

提示：

s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小写英文字母组成

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j, k)$ ，表示字符串 $s_1$ 从 $i$ 开始长度为 $k$ 的子串是否能变换为字符串 $s_2$ 从 $j$ 开始长度为 $k$ 的子串。如果能变换，返回 true，否则返回 false。那么答案就是 $dfs(0, 0, n)$ ，其中 $n$ 是字符串的长度。

函数 $dfs(i, j, k)$ 的计算方式如下：

如果 $k=1$ ，那么只需要判断 $s_1[i]$ 和 $s_2[j]$ 是否相等，如果相等返回 true，否则返回 false；
如果 $k \gt 1$ ，我们枚举分割部分的长度 $h$ ，那么有两种情况：如果不交换分割的两个子字符串，那么就是 $dfs(i, j, h) \land dfs(i+h, j+h, k-h)$ ；如果交换了分割的两个子字符串，那么就是 $dfs(i, j+k-h, h) \land dfs(i+h, j, k-h)$ 。如果两种情况中有一种情况成立，那么就说明 $dfs(i, j, k)$ 成立，返回 true，否则返回 false。

最后，我们返回 $dfs(0, 0, n)$ 。

为了避免重复计算，我们可以使用记忆化搜索的方式。

时间复杂度 $O(n^4)$ ，空间复杂度 $O(n^3)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i: int, j: int, k: int) -> bool:
            if k == 1:
                return s1[i] == s2[j]
            for h in range(1, k):
                if dfs(i, j, h) and dfs(i + h, j + h, k - h):
                    return True
                if dfs(i + h, j, k - h) and dfs(i, j + k - h, h):
                    return True
            return False

        return dfs(0, 0, len(s1))

speed

复杂度分析

指标	值
时间	O(n^4)
空间	O(n^3)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of dynamic programming by explaining the state transition approach and memoization.
question_mark
The candidate recognizes the importance of efficiently handling recursive calls using memoization to avoid recomputation.
question_mark
The candidate may struggle with the recursive nature of the problem if they fail to correctly identify the base cases or transitions.

warning

常见陷阱

外企场景

error
The candidate may overlook the importance of memoization, leading to a time complexity of O(n^6) instead of O(n^4).
error
Failing to account for both swap and non-swap scenarios in recursive calls can result in incorrect answers.
error
Not properly handling edge cases, such as when the strings are already identical or cannot be scrambled into one another, could lead to unnecessary computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the length of the strings beyond the current constraints to test the performance of the algorithm.
arrow_right_alt
Modifying the problem to check for scrambled substrings within a larger string rather than the whole string.
arrow_right_alt
Introducing additional characters or larger alphabets in the strings, potentially testing the space and time efficiency of the solution.

help

常见问题

外企场景

继续练习

#91 解码方法 #97 交错字符串 #72 编辑距离