Hard

题目描述

我们可以使用以下算法将字符串 s 扰乱成字符串 t：

  1. 如果字符串的长度为 1，停止。
  2. 如果字符串的长度 > 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 由小写英文字母组成

解题思路

这是一道经典的递归与动态规划问题。

思路分析：

首先理解扰乱字符串的规则：可以在任意位置将字符串分为两部分，然后选择是否交换这两部分，再对每部分递归进行相同操作。

解法有两种主要思路：

  1. 递归 + 记忆化搜索：对于两个字符串 s1[i:i+len] 和 s2[j:j+len]，尝试在每个可能的分割点 k 处分割，检查是否满足扰乱条件。有两种情况：

    • 不交换：s1[i:i+k] 对应 s2[j:j+k]，s1[i+k:i+len] 对应 s2[j+k:j+len]
    • 交换：s1[i:i+k] 对应 s2[j+len-k:j+len]，s1[i+k:i+len] 对应 s2[j:j+len-k]

  2. 三维动态规划：dp[i][j][len] 表示从 s1[i] 开始长度为 len 的子串是否可以扰乱成从 s2[j] 开始长度为 len 的子串。

为了优化性能，在递归前先进行字符频率检查，如果两个字符串包含的字符不同，直接返回 false。

推荐使用记忆化递归解法，代码更清晰易懂。

代码实现

class Solution {
public:
    unordered_map<string, bool> memo;
    
    bool isScramble(string s1, string s2) {
        if (s1.length() != s2.length()) return false;
        return helper(s1, s2);
    }
    
private:
    bool helper(string s1, string s2) {
        if (s1 == s2) return true;
        
        string key = s1 + "#" + s2;
        if (memo.count(key)) return memo[key];
        
        // 字符频率检查
        vector<int> count(26, 0);
        for (int i = 0; i < s1.length(); i++) {
            count[s1[i] - 'a']++;
            count[s2[i] - 'a']--;
        }
        for (int c : count) {
            if (c != 0) return memo[key] = false;
        }
        
        int n = s1.length();
        for (int i = 1; i < n; i++) {
            // 不交换的情况
            if (helper(s1.substr(0, i), s2.substr(0, i)) && 
                helper(s1.substr(i), s2.substr(i))) {
                return memo[key] = true;
            }
            // 交换的情况
            if (helper(s1.substr(0, i), s2.substr(n - i)) && 
                helper(s1.substr(i), s2.substr(0, n - i))) {
                return memo[key] = true;
            }
        }
        
        return memo[key] = false;
    }
};

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        
        memo = {}
        
        def helper(s1, s2):
            if s1 == s2:
                return True
            
            key = s1 + "#" + s2
            if key in memo:
                return memo[key]
            
            # 字符频率检查
            if sorted(s1) != sorted(s2):
                memo[key] = False
                return False
            
            n = len(s1)
            for i in range(1, n):
                # 不交换的情况
                if (helper(s1[:i], s2[:i]) and helper(s1[i:], s2[i:])):
                    memo[key] = True
                    return True
                # 交换的情况
                if (helper(s1[:i], s2[n-i:]) and helper(s1[i:], s2[:n-i])):
                    memo[key] = True
                    return True
            
            memo[key] = False
            return False
        
        return helper(s1, s2)

public class Solution {
    private Dictionary<string, bool> memo = new Dictionary<string, bool>();
    
    public bool IsScramble(string s1, string s2) {
        if (s1.Length != s2.Length) return false;
        return Helper(s1, s2);
    }
    
    private bool Helper(string s1, string s2) {
        if (s1 == s2) return true;
        
        string key = s1 + "#" + s2;
        if (memo.ContainsKey(key)) return memo[key];
        
        // 字符频率检查
        int[] count = new int[26];
        for (int i = 0; i < s1.Length; i++) {
            count[s1[i] - 'a']++;
            count[s2[i] - 'a']--;
        }
        foreach (int c in count) {
            if (c != 0) return memo[key] = false;
        }
        
        int n = s1.Length;
        for (int i = 1; i < n; i++) {
            // 不交换的情况
            if (Helper(s1.Substring(0, i), s2.Substring(0, i)) && 
                Helper(s1.Substring(i), s2.Substring(i))) {
                return memo[key] = true;
            }
            // 交换的情况
            if (Helper(s1.Substring(0, i), s2.Substring(n - i)) && 
                Helper(s1.Substring(i), s2.Substring(0, n - i))) {
                return memo[key] = true;
            }
        }
        
        return memo[key] = false;
    }
}

var isScramble = function(s1, s2) {
    if (s1.length !== s2.length) return false;
    if (s1 === s2) return true;
    
    const memo = new Map();
    
    function helper(s1, s2) {
        if (s1 === s2) return true;
        if (s1.length !== s2.length) return false;
        
        const key = s1 + '#' + s2;
        if (memo.has(key)) return memo.get(key);
        
        // Check if they have same characters
        const count = new Array(26).fill(0);
        for (let i = 0; i < s1.length; i++) {
            count[s1.charCodeAt(i) - 97]++;
            count[s2.charCodeAt(i) - 97]--;
        }
        for (let i = 0; i < 26; i++) {
            if (count[i] !== 0) {
                memo.set(key, false);
                return false;
            }
        }
        
        // Try all possible splits
        for (let i = 1; i < s1.length; i++) {
            // Case 1: no swap
            if (helper(s1.slice(0, i), s2.slice(0, i)) && 
                helper(s1.slice(i), s2.slice(i))) {
                memo.set(key, true);
                return true;
            }
            
            // Case 2: swap
            if (helper(s1.slice(0, i), s2.slice(s2.length - i)) && 
                helper(s1.slice(i), s2.slice(0, s2.length - i))) {
                memo.set(key, true);
                return true;
            }
        }
        
        memo.set(key, false);
        return false;
    }
    
    return helper(s1, s2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(4^n)，其中 n 是字符串长度。在最坏情况下，每个子问题都需要尝试所有可能的分割点
空间复杂度O(4^n)，记忆化存储的空间和递归调用栈的空间