LeetCode87——Scramble String

墨蓝 2022-08-20 13:29 101阅读 0赞

# LeetCode87——Scramble String #

## 原题 ##

> Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
> 
> Below is one possible representation of s1 = “great”:
> 
> great  
> / \\  
> gr eat  
> / \\ / \\  
> g r e at  
> / \\  
> a t  
> To scramble the string, we may choose any non-leaf node and swap its two children.
> 
> For example, if we choose the node “gr” and swap its two children, it produces a scrambled string >”rgeat”.
> 
> rgeat  
> / \\  
> rg eat  
> / \\ / \\  
> r g e at  
> / \\  
> a t  
> We say that “rgeat” is a scrambled string of “great”.
> 
> Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled >string “rgtae”.
> 
> rgtae  
> / \\  
> rg tae  
> / \\ / \\  
> r g ta e  
> / \\  
> t a  
> We say that “rgtae” is a scrambled string of “great”.

--------------------

## 分析 ##

着实想了一番，一开始想简单了，以为就是简单的交换顺序，那么求出s1的全排列，然后看s2在不在里面就ok，首先肯定是超时，但是尽管不超时，这种方法也是错误，因为这种二叉树左右孩子的交换不能简单的用全排列来表示（虽然在某些场合可以）。

那么就要考虑其他的办法了，想到二叉树的递归定义，也就是左子树右子树分别都是二叉树，根据此，那么首先假设s1=“abcd” s2=“bcda” 分别考虑左右子数元素的个数，以s1为基础，  
左子树元素(用s11表示)个数1 右子树元素(用s12表示)个数为3  
那么s11=”a” s12=”bcd”  
对于s2来说，我们就要分两种情况了（因为左右子数是可以交换的嘛）：  
1. 左子树元素个数为1 右子树元素个数为3  
2. 左子树元素个数为3 右子树元素个数为1

分别递归进行`isScramble(s11, s21) && isScramble(s12, s22)`和`isScramble(s11, s22) && isScramble(s12, s21)`运算，当然要设置递归返回条件：  
首先当比较的子串长度不一样的时候，这俩子串肯定不是”Scramble”，其次当递归到长度为1时如果这俩子串相等则返回true，否则false

--------------------

## 代码 ##

递归方式，有一点需要注意的是一旦返回true时一定要及时返回，否则递归会一直进行下去（尽管已经找到俩字符串满足Scramble的条件了），程序就是超时。

class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            if (s1.size() == 1)
                return s1 == s2;
            string str1 = s1;
            string str2 = s2;
            sort(str1.begin(), str1.end());
            sort(str2.begin(), str2.end());
            for (int i = 0; i < str1.size(); i++)//减少递归次数，元素不相等的串肯定不满足
            {
                if (str1[i] != str2[i])
                    return false;
            }
            string s11, s12;
            string s21, s22;
            bool result = false;
            for (int i = 1; i < s1.size(); i++)
            {
                s11 = s1.substr(0, i);
                s12 = s1.substr(i, s1.size() - i);
                s21 = s2.substr(0, i);
                s22 = s2.substr(i, s2.size() - i);
                result = isScramble(s11, s21) && isScramble(s12, s22);
                if(result)//及时返回
                    return true;
                else//为false的时候交换左右子树
                {
                    s21 = s2.substr(0, s2.size() - i);
                    s22 = s2.substr(s2.size() - i, i);
                    result = isScramble(s11, s22) && isScramble(s12, s21);
                    if(result)//及时返回
                        return true;
                }
            }
            return result;
        }
    };

--------------------

## 后记 ##

网上有用三次动态规划解决的算法，动态规划一直不是我的强项，找时间得学习一波，到时候再补充。