扰乱字符串题解。

目录

  1. 题目：扰乱字符串
  2. 解题思路：递归
  3. LeetCode 运行结果
  4. 代码

题目：扰乱字符串

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

下图是字符串 s1 = “great” 的一种可能的表示形式。

1
2
3
4
5
6
7
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。

例如，如果我们挑选非叶节点 “gr” ，交换它的两个子节点，将会产生扰乱字符串 “rgeat” 。

1
2
3
4
5
6
7
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

我们将 “rgeat” 称作 “great” 的一个扰乱字符串。

同样地，如果我们继续交换节点 “eat” 和 “at” 的子节点，将会产生另一个新的扰乱字符串 “rgtae” 。

1
2
3
4
5
6
7
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

我们将 “rgtae” 称作 “great” 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

示例 1:

1
2
输入: s1 = "great", s2 = "rgeat"
输出: true

示例 2:

1
2
输入: s1 = "abcde", s2 = "caebd"
输出: false

来源：力扣（LeetCode）。链接：https://leetcode-cn.com/problems/scramble-string

解题思路：递归

由于无法得知原字符串分割的位置，所以通过蛮力遍历每一个位置对原字符串进行分割，然后比较原字符串和扰乱字符串分割之后的子串是否相等。子串同样进行了分割，则需要再对子串进行分割判断。这个时候就可以使用递归了。

由于分割之后还可能进行交换，所以需要判断两种情况：

  1. 直接对原字符串进行分割，比较原字符串和扰乱字符串分割之后的子串是否相等。即s1[0, i] == s2[0, i] && s1[i+1, len - 1] == s2[i+1, len -1]。
  2. 将分割后的两个子串交换，然后比较交换后的子串。s1[0, i] == s2[len-1 - i, len-1] && s1[i+1, len - 1] == s2[0, len-i]。

优化：
由于分割交换并不会改变字符串中字符的个数，所以可以通过统计并比较两字符串中各字符的个数是否相等做一次筛选。
如果不等，则一定不是扰乱字符串。这是一个 __必要条件__。

LeetCode 运行结果

  • 执行用时 :8 ms, 在所有 C++ 提交中击败88.36的用户。
  • 内存消耗 :10 MB, 在所有 C++ 提交中击败了78.16%的用户。

代码

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
61
62
63
class Solution
{
public:
    bool isScramble(string s1, string s2)
    {
        if (s1.size() <= 1)
        {
                if (s1 == s2)
                {
                        return true;
                }
        }
        else
        {
                return _isScramble(s1, s2);
        }

        return false;
    }

    bool _isScramble(string s1, string s2)
    {                       
        int m = s1.length();
        if(s1 == s2)
        {
            return true;
        }

        //统计s1和s2的字符个数，判断相应的字符个数是否相等。（必要条件）
        int char_num[26] = {0};
        for(int i=0; i<m;i++)
        {
            char_num[s1[i] - 'a']++;
            char_num[s2[i] - 'a']--;
        }

        for(int i=0; i<26; i++)
        {
            if(char_num[i] != 0)
            {
                return false;
            }
        }

        for (int i = 0; i < m-1; i++)
        {
            //蛮力切割
            if ((_isScramble(s1.substr(0, i+1), s2.substr(0, i+1)) &&
            _isScramble(s1.substr(i + 1, m - (i + 1)), s2.substr(i + 1, m - (i + 1)))) == 1)
            {
                return true;
            }

            //切割并且交换
            if ((_isScramble(s1.substr(0, i+1), s2.substr(m-(i+1), i+1)) &&
            _isScramble(s1.substr(i + 1, m - (i + 1)), s2.substr(0, m - (i + 1)))) == 1)
            {
                return true;
            }
        }
        return false;
    }
};