LeetCode 87：扰乱字符串

LeetCode 87：扰乱字符串

问题定义与核心挑战

给定两个长度相同的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。扰乱字符串的生成规则是：

1. 若字符串长度为 1，无法分割。
2. 若长度 >1，将字符串分割为两个非空子串 x 和 y，然后交换或保持 x 和 y 的顺序，递归处理子串。

核心挑战：

• 递归重复计算：直接递归会因大量重复子问题导致超时。
• 高效状态表示：如何避免频繁的字符串切片操作，优化空间和时间复杂度。

核心思路：动态规划 + 记忆化搜索

利用 动态规划（DP） 分解问题，结合 记忆化搜索 缓存子问题结果，同时通过 字符频率剪枝 提前排除不可能的情况：

1. 状态定义：dp[i1][i2][len] 表示 s1 从 i1 开始、s2 从 i2 开始、长度为 len 的子串是否为扰乱字符串（-1 未计算，0 否，1 是）。
2. 状态转移：遍历所有分割点，判断“不交换子串”和“交换子串”两种情况。
3. 字符频率剪枝：若子串的字符组成不同，直接返回 false（必要条件）。

算法步骤详解

步骤 1：状态定义与初始化

• 三维数组 dp：dp[i1][i2][len] 存储子问题结果，避免重复计算。
• 初始化：所有元素设为 -1（表示未计算）。

int[][][] dp; // 三维数组，-1:未算，0:否，1:是

步骤 2：字符频率检查（剪枝）

扰乱字符串的字符组成必须完全相同。通过统计子串的字符频率，提前排除不可能的情况：

private boolean checkFrequency(int i1, int i2, int len) {
    int[] count = new int[26]; // 统计小写字母频率
    for (int i = 0; i < len; i++) {
        char c1 = s1.charAt(i1 + i);
        char c2 = s2.charAt(i2 + i);
        count[c1 - 'a']++;
        count[c2 - 'a']--;
    }
    for (int cnt : count) {
        if (cnt != 0) return false; // 频率不同，直接剪枝
    }
    return true;
}

步骤 3：记忆化搜索（递归 + 状态转移）

递归处理每个子串，根据分割点判断两种情况：

1. 递归终止条件：
   • 若子串长度为 1，且字符频率相同（已通过剪枝），则必然是扰乱字符串。
2. 状态转移：
   • 不交换子串：s1 的前 k 个与 s2 的前 k 个匹配，剩余部分也匹配。
   • 交换子串：s1 的前 k 个与 s2 的后 k 个匹配，剩余部分与 s2 的前 len-k 个匹配。

完整递归逻辑

private int dfs(int i1, int i2, int len) {
    if (dp[i1][i2][len] != -1) {
        return dp[i1][i2][len]; // 记忆化回溯
    }

    // 字符频率不同，直接返回false
    if (!checkFrequency(i1, i2, len)) {
        dp[i1][i2][len] = 0;
        return 0;
    }

    // 长度为1，必然是扰乱字符串（频率已匹配）
    if (len == 1) {
        dp[i1][i2][len] = 1;
        return 1;
    }

    // 遍历所有分割点k（1 <= k < len）
    for (int k = 1; k < len; k++) {
        // 情况1：不交换子串顺序
        if (dfs(i1, i2, k) == 1 && dfs(i1 + k, i2 + k, len - k) == 1) {
            dp[i1][i2][len] = 1;
            return 1;
        }
        // 情况2：交换子串顺序
        if (dfs(i1, i2 + len - k, k) == 1 && dfs(i1 + k, i2, len - k) == 1) {
            dp[i1][i2][len] = 1;
            return 1;
        }
    }

    // 所有分割点都不满足
    dp[i1][i2][len] = 0;
    return 0;
}

完整代码（Java）

import java.util.Arrays;

class Solution {
    private String s1, s2;
    private int[][][] dp; // dp[i1][i2][len]: -1未算，0否，1是

    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        this.s1 = s1;
        this.s2 = s2;
        int n = s1.length();
        // 初始化三维DP数组
        dp = new int[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return dfs(0, 0, n) == 1;
    }

    private int dfs(int i1, int i2, int len) {
        if (dp[i1][i2][len] != -1) {
            return dp[i1][i2][len]; // 记忆化回溯
        }

        // 检查字符频率，剪枝
        if (!checkFrequency(i1, i2, len)) {
            dp[i1][i2][len] = 0;
            return 0;
        }

        // 长度为1，必然匹配（频率已保证）
        if (len == 1) {
            dp[i1][i2][len] = 1;
            return 1;
        }

        // 遍历所有分割点k
        for (int k = 1; k < len; k++) {
            // 情况1：不交换子串顺序
            if (dfs(i1, i2, k) == 1 && dfs(i1 + k, i2 + k, len - k) == 1) {
                dp[i1][i2][len] = 1;
                return 1;
            }
            // 情况2：交换子串顺序
            if (dfs(i1, i2 + len - k, k) == 1 && dfs(i1 + k, i2, len - k) == 1) {
                dp[i1][i2][len] = 1;
                return 1;
            }
        }

        // 无有效分割点
        dp[i1][i2][len] = 0;
        return 0;
    }

    private boolean checkFrequency(int i1, int i2, int len) {
        int[] count = new int[26];
        for (int i = 0; i < len; i++) {
            char c1 = s1.charAt(i1 + i);
            char c2 = s2.charAt(i2 + i);
            count[c1 - 'a']++;
            count[c2 - 'a']--;
        }
        for (int cnt : count) {
            if (cnt != 0) return false;
        }
        return true;
    }
}

关键逻辑解析

1. 状态优化：索引 + 长度

• 用 i1（s1 起始索引）、i2（s2 起始索引）、len（子串长度）表示状态，避免频繁的字符串切片操作，大幅优化空间和时间复杂度。

2. 记忆化搜索的作用

• 缓存已计算的子问题结果（dp[i1][i2][len]），避免重复递归，将时间复杂度从 指数级 降至 多项式级。

3. 字符频率剪枝的必要性

• 扰乱字符串的字符组成必须完全相同，若频率不同可直接返回 false，减少无效递归。

4. 状态转移的两种情况

• 不交换子串：子串顺序与原字符串一致，需两边子串分别匹配。
• 交换子串：子串顺序反转，需交叉匹配两边子串。

示例验证（以示例 1 为例）

输入：s1 = "great", s2 = "rgeat"（假设正确示例，实际需符合扰乱规则）

1. 字符频率检查：两者字符均为 g, r, e, a, t，频率相同。
2. 递归分割：当 len=5，i1=0，i2=0 时，遍历分割点 k=2：
   • 交换情况：s1 的前 2 个字符（"gr"）与 s2 的后 2 个字符（"at" 不匹配，此处仅为示例逻辑），最终通过递归找到有效分割点，返回 true。

该方法通过 动态规划 + 记忆化搜索 + 字符频率剪枝，高效解决了扰乱字符串的判断问题，平衡了递归的灵活性和效率，是处理复杂递归问题的经典思路。