离职把代码注释全删了，算违法吗？

今天我们来聊聊一个经典的算法题——“扰乱字符串”。这题一开始看上去很简单，但在细细琢磨后，你会发现其中有很多需要注意的细节，尤其是处理递归和动态规划时。

别急，接下来我会用我自己理解的方式来带大家过一遍这个问题。希望你看完之后，能够轻松应对类似的面试题！

问题描述

给你两个字符串 s1 和 s2，判断 s2 是否是 s1 的一个扰乱字符串。所谓的扰乱字符串就是你可以通过多次交换 s1 中的字符顺序，得到 s2。

举个简单例子：

• • s1 = "abcde"
• • s2 = "caebd"

你可能会想，这俩能通过字符交换变成一样的吗？可以！只要你理解扰乱的过程，就能看出这两者之间的关系。

思路剖析

想要解决这个问题，首先我们要明确什么是扰乱字符串。一个字符串的扰乱就是指通过交换字符串中的一部分字符位置，可以得到另一个字符串。因此，判断 s2 是否是 s1 的扰乱字符串，可以分为以下两步：

1. 1. 字符计数：如果 s1 和 s2 字符不一样，那么不可能是扰乱字符串。比如，abc 和 abcc 不可能是互为扰乱字符串的。
2. 2. 递归判断：这才是关键。假设我们把字符串一分为二，然后判断这两部分能不能交换得到对方。你会发现这其实是一个典型的递归问题：我们需要判断左半部分和右半部分的关系，同时还要考虑字符交换的影响。

动态规划（DP）解法

一开始我也想过用暴力递归来解这个题。因为通过分割字符串来进行判断，感觉递归是最直观的方法。但暴力递归的时间复杂度会很高，导致效率太低。于是，我决定改用动态规划来优化它。

DP 转移方程

我们用 dp[i][j][l] 来表示，s1 从第 i 个字符到第 i+l-1 个字符，是否能够通过扰乱变成 s2 从第 j 个字符到第 j+l-1 个字符。

基本的转移是：

• • 如果这两个字符串不一样长，直接返回 false。
• • 如果我们选择分割字符串后递归，判断左半部分和右半部分的关系。

代码实现

publicclass Solution {
public boolean isScramble(String s1, String s2) {
// 长度不同直接返回 false
if (s1.length() != s2.length()) {
returnfalse;
        }

int n= s1.length();
// dp[i][j][l] 表示s1从i位置开始长度为l的子串是否能变成s2从j位置开始长度为l的子串
boolean[][][] dp = newboolean[n][n][n + 1];

// 初始条件：长度为1的子串
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }

// 动态规划：从长度为2到n
for (int len=2; len <= n; len++) {
for (int i=0; i <= n - len; i++) {
for (int j=0; j <= n - len; j++) {
// 分割点
for (int k=1; k < len; k++) {
// 递归判断两种情况
if ((dp[i][j][k] && dp[i + k][j + k][len - k]) || 
                            (dp[i][j + len - k][k] && dp[i + k][j][len - k])) {
                            dp[i][j][len] = true;
break;
                        }
                    }
                }
            }
        }

return dp[0][0][n];
  }

解释

1. 1. dp[i][j][l]：表示 s1 中从第 i 个字符开始，长度为 l 的子串，是否能通过扰乱变成 s2 中从第 j 个字符开始，长度为 l 的子串。
2. 2. 初始化：当长度为 1 时，我们直接判断两个字符是否相等。如果相等，dp[i][j][1] 就是 true。
3. 3. 状态转移：对于每一个长度为 l 的子串，我们会尝试分割该子串为两部分。然后递归地检查这两部分是否能通过扰乱互换位置。分割点的选择非常关键，我们有两种可能的交换方式：

• • 第一种交换方式：左部分和左部分匹配，右部分和右部分匹配。
• • 第二种交换方式：左部分和右部分匹配，右部分和左部分匹配。

复杂度分析

• • 时间复杂度：O(n^4)。其中，n 是字符串的长度。我们有三个循环，分别控制分割位置和子串的长度。每次判断都需要遍历一遍分割的所有情况。
• • 空间复杂度：O(n^3)。我们需要一个三维的动态规划数组 dp 来保存中间结果。

总结

扰乱字符串这道题，乍一看简单，但深入思考后你会发现，理解它的本质需要一定的技巧。通过动态规划，我们有效地解决了暴力递归的时间复杂度问题，优化了算法的性能。

如果你想要掌握类似的技巧，掌握动态规划就非常重要。每次遇到递归问题时，考虑是否可以通过动态规划来缓存结果，从而提高效率。