leetcode做题笔记87扰乱字符串-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记87扰乱字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

使用下面描述的算法可以扰乱字符串 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 。

思路一：模拟题意

bool check(char *s1,char *s2,int len)
{
    char ss1[26]={0};
    char ss2[26]={0};
    char i=0;
    for (i=0;i<len;i++)
    {
        ss1[s1[i]-'a']++;
        ss2[s2[i]-'a']++;
    }
    for(i=0;i<26;i++)
    {
        if(ss1[i]!=ss2[i]) return false;
    }
    return true;
}
char mem[30][30][31];
bool complie(char *s1,char *s2,int len,int s1begin,int s2begin)
{
    if(mem[s1begin][s2begin][len]==1) return true;
    if(mem[s1begin][s2begin][len]==2) return false;
    if(len==0) return true;
    if(len==1) {mem[s1begin][s2begin][len]=1;return *s1==*s2;}
    if(!check(s1,s2,len)) {mem[s1begin][s2begin][len]=2;return false;}
    int i=0;
    for(i=1;i<len;i++)
    {
        if(complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)) {
            mem[s1begin][s2begin][len]=1;
            return true;}
        if(complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin)) {
            mem[s1begin][s2begin][len]=1;
            return true;}
    }
    mem[s1begin][s2begin][len]=2;
    return false;
}
bool isScramble(char * s1, char * s2){
    int len1=0;
    int len2=0;
    memset(mem,0,sizeof(mem));
    while(s1[len1]!=0)
    {
        len1++;
    }
    while(s2[len2]!=0)
    {
        len2++;
    }
    if(len1!=len2) return false;
    return complie(s1,s2,len1,0,0);
}

分析：

本题扰乱字符串满足交换两个子字符串或保持这两个子字符串的顺序不变，转换为complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)和complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin)，通过complie函数递归找到答案，同时两个字符串长度首先要相等，先判断两个字符串长度是否相等再进行递归返回答案