判断s2是否为s1的乱序字符串

---

刷题平台

牛客网

题目描述

题目给出一个字符串s1，我们可以用递归的方法将字符串分成两个非空的子串来将s1表示成一个二叉树

下面是s1=“great”的一种二叉树的表现形式：

great↵   /    ↵  gr    eat↵ /     /  ↵g   r  e   at↵           / ↵          a   t

将字符串乱序的方法是：选择任意的非叶子节点，交换它的两个孩子节点。

例如：如果我们选择节点“gr”交换他的两个孩子节点，就会产生一个乱序字符串”rgeat”.

rgeat↵ / ↵ rg eat↵ / / ↵r g e at↵ / ↵ a t我们称”rgeat”是”great”的一个乱序字符串。类似的：如果我们继续交换“eat”的两个孩子节点和“at”的两个孩子节点，会产生乱序字符串”rgtae”.

rgtae↵ / ↵ rg tae↵ / / ↵r g ta e↵ / ↵ t a我们称”rgtae”是”great”的一个乱序字符串。
给出两个长度相同的字符串s1 和 s2，请判断s2是否是s1的乱序字符串。

解题思路

本题的主要目的就是为了判断给出的两个字符串的字符是否全部相同。

那么如何判断两个字符串中的字符是相同呢（和字符串相等不同）？

​ 如果是判断两个字符串是否相等，可以通过循环遍历得到结果。但是本题中两个字符串包含相同字符但是顺序不同的情况。这就不能通过简单的循环遍历比较得到是否相等了。考虑到所给字符串可能都是字母的情况（这可能只是个特例）如下代码中的方法判断两个字符串中的元素是否相同（无序比较）

vector<int> dp(26, 0); 
for (int i = 0; i < s1.size(); i++)
{
	dp[s1[i] - 'a']++;
    dp[s2[i] - 'a']--;
}
for (int i = 0; i < 26; i++)
    if (dp[i] != 0)
       return false;

解决了如何判断字符串中元素是否相同的问题，那么如何解决s2是否为s1的乱序字符串的问题呢？

如题中给的例子：s1 = "great"；通过将s1转换为二叉树的形式可以进行如下分割：

gr | eat 那么它的乱序字符串s2可以是 rg | eat或者eat | gr等。不妨假设s1中的前部gr为s11，后部eat为s12；s2中的前部rg为s21，后部eat为s22或者s2中的前部eat为s21，后部gr为s22；

通过递归思想，依次比较分割乱序后的每部分是否同样满足字符全部相同的条件，即s11与s21/s22，s12与s22/s21是否满足条件。

代码

class Solution
{
public:
    bool isScramble (string s1, string s2)
    {
        if (s1 == s2)
            return true;
        
        vector<int> dp(26, 0);//构造一个26位的数组，用于存放字符串中字符出现的次数
        for (int i = 0; i < s1.size(); i++)
        {
            dp[s1[i] - 'a']++;
            dp[s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (dp[i] != 0)
                return false;
        
        for (int i = 1; i < s1.size(); i++)
        {
            if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)) || 
                isScramble(s1.substr(0, i), s2.substr(s2.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
                return true;
        }
        return false;
    }
};

参考链接：

https://www.nowcoder.com/questionTerminal/2bdc44bb0186468b8d8c13ea5d3a9e58?f=discussion