扰乱题库

扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 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

整体思路: [扰乱字符串]的关系是具有对称性的，如果s1是s2的扰乱字符串，那么s2也是s1的扰乱字符串。我们称这种情况下，s1和s2是和谐的。

如何判断s1和s2是否和谐呢？

如果s1=s2,那么它们是和谐的
如果s1和s2的长度不同，那么它们一定不是和谐的
如果s1中某个字符c出现了x1次，而c在s2中出现了x2次，且x1!=x2,那么他们一定不是和谐的。
那么对于剩下的情况，我们该如何判断呢？

方案动态规划

思路:

状态定义: dp[s1][s2]表示s1和s2是否和谐
状态转移方程:
- 如果s1=s2,则方程为: dp[s1][s2]=true
- 如果存在某个字符c,它在s1和s2中的出现次数不同，则方程为: dp[s1][s2]=false
- 如果l(s1)和r(s1)没有被交换时，s2同样需要被分为s2(0,i)以及s2(i,n-i),否则长度不同的字符串是不可能和谐的，则方程为:dp[s1,s2]=dp[s1(0,i),s2(0,i)]&&dp[s1(i,n-i),s2(i,n-i)
- 如果l(s1)和r(s1)被交换时，s2需要被分为s2(0,n-i)以及s2(n-i,i)，这样对应的长度才会相同，则方程为:dp[s1,s2]=dp[s1(0,i),s2(n-i,i)]&&dp[s1(i,n-i),,s2(0,n-i)]
初始化状态:
问题答案：

:::details 点击查看代码

function dfs(i1,i2,len,s1,s2,dp){
    if(dp[i1][i2][len]!==0){
        return dp[i1][i2][len]==1;
    }
    if(s1.slice(i1,i1+len)===s2.slice(i2,i2+len)){
        dp[i1][i2][len]=1;
        return true;
    }
    if(!checkIfSimilar(i1,i2,len,s1,s2)){
        dp[i1][i2][len]=-1;
        return false;
    }
    for(let i=1;i<len;i++){
        if(dfs(i1,i2,i,s1,s2,dp)&&dfs(i1+i,i2+i,len-i,s1,s2,dp)){
            dp[i1][i2][len]=1;
            return true;
        }
        if(dfs(i1,i2+len-i,i,s1,s2,dp)&&dfs(i1+i,i2,len-i,s1,s2,dp)){
            dp[i1][i2][len]=1;
            return true;
        }
    }
    dp[i1][i2][len]=-1;
    return false;
}
function checkIfSimilar(i1,i2,len,s1,s2){
    const freq=new Map();
    for(let i=i1;i<i1+len;i++){
        const c=s1[i];
        freq.set(c,(freq.get(c)||0)+1);
    }
    for(let i=i2;i<i2+len;i++){
        const c=s2[i];
        freq.set(c,(freq.get(c)||0)-1);
    }
    for(const value of freq.values()){
        if(value!==0){
            return false;
        }
    }
    return true;
}
function isScramble(s1,s2){
    const len=s1.length;
    const dp=new Array(len).fill(0).map(()=>new Array(len).fill(0).map(()=>new Array(len+1).fill(0)));
    return dfs(0,0,len,s1,s2,dp);
}

:::

性能分析:

时间复杂度：O(n^4)
空间复杂度：O(n^3)

扰乱字符串​

方案 动态规划​

扰乱字符串

方案动态规划