LeetCode 87:扰乱字符串

发布于:2025-07-29 ⋅ 阅读:(21) ⋅ 点赞:(0)

LeetCode 87:扰乱字符串

在这里插入图片描述

问题定义与核心挑战

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

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

核心挑战:

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

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

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

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

算法步骤详解

步骤 1:状态定义与初始化
  • 三维数组 dpdp[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. 状态优化:索引 + 长度
  • i1s1 起始索引)、i2s2 起始索引)、len(子串长度)表示状态,避免频繁的字符串切片操作,大幅优化空间和时间复杂度。
2. 记忆化搜索的作用
  • 缓存已计算的子问题结果(dp[i1][i2][len]),避免重复递归,将时间复杂度从 指数级 降至 多项式级
3. 字符频率剪枝的必要性
  • 扰乱字符串的字符组成必须完全相同,若频率不同可直接返回 false,减少无效递归。
4. 状态转移的两种情况
  • 不交换子串:子串顺序与原字符串一致,需两边子串分别匹配。
  • 交换子串:子串顺序反转,需交叉匹配两边子串。

示例验证(以示例 1 为例)

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

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

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


网站公告

今日签到

点亮在社区的每一天
去签到