Leetcode-87.扰乱字符串

发表于 分类于 阅读次数：

题目链接:https://leetcode-cn.com/problems/scramble-string/

解法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.length()!=s2.length())
        {
            return false;
        }
        if(s1==s2)
            return true;
        int f[26]={0};
        int i,a,b;
         //判断两个字符串每个字母出现的次数是否一致
        for(i=0;i<s1.length();i++)
        {
            a=s1[i]-'a';
            b=s2[i]-'a';
            f[a]++;
            f[b]--;
        }
        //如果两个字符串的字母出现不一致直接返回 false
        for(i=0;i<26;i++)
        {
            if(f[i]!=0)
                return false;
        }
        //遍历每个切割位置
        for(i=1;i<s1.length();i++)
        {
            //对应情况 1 ，判断 S1 的子树能否变为 S2 相应部分
                if(isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i,s1.length()),s2.substr(i,s2.length())))
            {
                return true;
            }
            //对应情况 2 ，S1 两个子树先进行了交换，然后判断 S1 的子树能否变为 S2 相应部分
            if(isScramble(s1.substr(0,i),s2.substr(s2.length()-i,i))&&isScramble(s1.substr(i,s1.length()),s2.substr(0,s2.length()-i)))
            {
                return true;
            }
        }
        return false;
    }
};

解法2：记录化递归

理论上记录下递归应该比没有记录要快但在leetcode上反而不如前面快，可能是构建字符串会浪费一定的时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:
    map<string,int> m;
public:
    bool isScramble(string s1, string s2) {
        map<string,int>::iterator iter;
        iter=m.find(s1+'#'+s2);
        if(iter!=m.end())
        {
            if(iter->second==0)
                return false;
            else if(iter->second==1)
                return true;
                
        }
        if(s1.length()!=s2.length())
        {
            m.insert(pair<string,int>(s1+'#'+s2,0)); 
            return false;
        }
        if(s1==s2)
        {
            m.insert(pair<string,int>(s1+'#'+s2,1)); 
            return true;
            
        }
        int f[26]={0};
        int i,a,b;
        for(i=0;i<s1.length();i++)
        {
            a=s1[i]-'a';
            b=s2[i]-'a';
            f[a]++;
            f[b]--;
        }
        for(i=0;i<26;i++)
        {
            if(f[i]!=0)
            {
                m.insert(pair<string,int>(s1+'#'+s2,0));    
                return false;
            }
        }
        for(i=1;i<s1.length();i++)
        {
                if(isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i,s1.length()),s2.substr(i,s2.length())))
            {
                m.insert(pair<string,int>(s1+'#'+s2,1)); 
                return true;
            }
            if(isScramble(s1.substr(0,i),s2.substr(s2.length()-i,i))&&isScramble(s1.substr(i,s1.length()),s2.substr(0,s2.length()-i)))
            {
                 m.insert(pair<string,int>(s1+'#'+s2,1)); 
                return true;
            }
        }
        m.insert(pair<string,int>(s1+'#'+s2,0)); 
        return false;
    }
};

https://leetcode-cn.com/problems/scramble-string/