LeetCode 扰乱字符串：深入解析及Python高效解法382

LeetCode 的 "扰乱字符串" 问题 (Scramble String) 是一道经典的动态规划题目，考察了递归、记忆化搜索以及动态规划等多种算法技巧。题目描述如下：给定两个字符串 s1 和 s2，长度相同。如果我们可以通过扰乱 s1 的字母顺序得到 s2，则返回 true；否则，返回 false。扰乱字符串的规则是：你可以将字符串分成两部分，交换这两部分的顺序，然后递归地扰乱每一部分。例如，"great" 可以扰乱成 "rgeat" （将 "gr" 和 "eat" 分开，交换顺序），然后 "rgeat" 可以扰乱成 "grtae" （将 "rg" 和 "eat" 分开，交换顺序），最终得到 "great" 的一个扰乱字符串。

这道题目的难点在于如何有效地判断两个字符串是否可以通过扰乱得到。暴力递归的方法会造成指数级的复杂度，导致超时。因此，我们需要寻找更有效的算法。本文将深入探讨这个问题的解法，从递归、记忆化搜索到动态规划，逐步提升算法效率，并提供清晰易懂的 Python 代码实现。

一、暴力递归法

最直观的思路是使用递归。我们枚举字符串的所有可能的分割点，交换子串，然后递归地判断两个子串是否可以通过扰乱得到。代码如下：```python
def isScramble_recursive(s1, s2):
"""暴力递归法，效率极低"""
if len(s1) != len(s2):
return False
if len(s1) == 0:
return True
if sorted(s1) != sorted(s2): # 优化：如果字符不相同，直接返回 False
return False
for i in range(1, len(s1)):
if (isScramble_recursive(s1[:i], s2[:i]) and isScramble_recursive(s1[i:], s2[i:])) or \
(isScramble_recursive(s1[:i], s2[len(s1)-i:]) and isScramble_recursive(s1[i:], s2[:len(s1)-i])):
return True
return False
```

这段代码虽然简洁，但时间复杂度高达 O(3nn2)，其中 n 是字符串长度。对于较长的字符串，其效率非常低，很容易超时。

二、记忆化搜索

为了提升效率，我们可以使用记忆化搜索来避免重复计算。我们使用一个字典来存储已经计算过的结果，如果遇到已经计算过的子问题，直接返回结果，避免重复计算。```python
from functools import lru_cache
@lru_cache(None)
def isScramble_memo(s1, s2):
"""记忆化搜索"""
if len(s1) != len(s2):
return False
if len(s1) == 0:
return True
if sorted(s1) != sorted(s2):
return False
for i in range(1, len(s1)):
if (isScramble_memo(s1[:i], s2[:i]) and isScramble_memo(s1[i:], s2[i:])) or \
(isScramble_memo(s1[:i], s2[len(s1)-i:]) and isScramble_memo(s1[i:], s2[:len(s1)-i])):
return True
return False
```

使用 `@lru_cache` 装饰器可以方便地实现记忆化搜索，大大减少了计算量，提高了算法效率。虽然时间复杂度仍然是指数级的，但实际运行速度会有显著提升。

三、动态规划

动态规划是解决此问题的最有效方法。我们可以定义一个三维数组 `dp[i][j][k]`，表示字符串 `s1` 从 `i` 开始长度为 `k` 的子串是否可以扰乱成字符串 `s2` 从 `j` 开始长度为 `k` 的子串。状态转移方程如下：

dp[i][j][k] = True 当且仅当存在一个 `l` (1 ≤ `l` < `k`) 使得：
dp[i][j][l] == True 且 dp[i+l][j+l][k-l] == True
或者 dp[i][j+k-l][l] == True 且 dp[i+l][j][k-l] == True

Python 代码实现如下：```python
def isScramble_dp(s1, s2):
"""动态规划法"""
n = len(s1)
if len(s2) != n:
return False
if sorted(s1) != sorted(s2):
return False
dp = [[[False for _ in range(n + 1)] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
dp[i][j][1] = (s1[i] == s2[j])
for k in range(2, n + 1):
for i in range(n - k + 1):
for j in range(n - k + 1):
for l in range(1, k):
if (dp[i][j][l] and dp[i + l][j + l][k - l]) or \
(dp[i][j + k - l][l] and dp[i + l][j][k - l]):
dp[i][j][k] = True
break
return dp[0][0][n]
```

动态规划法的时间复杂度为 O(n4)，空间复杂度为 O(n3)。虽然复杂度比记忆化搜索高，但在处理大规模输入时，其性能会更加稳定和高效，因为避免了递归调用的开销。

四、总结

本文详细介绍了 LeetCode 扰乱字符串问题的三种解法：暴力递归、记忆化搜索和动态规划。虽然暴力递归法简单易懂，但效率极低；记忆化搜索能有效提高效率，但仍然是指数级复杂度；动态规划法拥有较高的时空复杂度，但能保证在面对大规模输入时也能稳定高效地解决问题。选择哪种方法取决于实际应用场景和对效率的要求。对于大多数情况，动态规划法是解决此问题的最佳选择。

2025-06-17

上一篇：Python中的分数运算：fraction模块详解及高级应用

下一篇：Python字符串分割与Map函数的高效结合