Leetcode No.87 ***

ゞ浴缸里的玫瑰 2021-12-01 09:59 239阅读 0赞

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

示例 1:

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

示例 2:

输入: s1 = "abcde", s2 = "caebd"
    输出: false
    
    解答：本题可以用递归算法来处理。递归函数的逻辑如下：
    【1】对字符串进行排序，比较排序后字符串是否相等
    【2】对字符串进行切割，判断正对比是否符合要求（递归）；判断反对比是否符合要求（递归）；
    【3】若否，返回false;

//87
    bool isScramble(string s1, string s2)
    {
        if(s1 == s2) return true;
        if(s1.size()!=s2.size()) return false;
        string str1 = s1, str2 = s2;
        sort(str1.begin(),str1.end());
        sort(str2.begin(),str2.end());
        if(str1 != str2) return false;
        for(int i=1;i<(signed)s1.size();i++)
        {
            string s11 = s1.substr(0,i);
            string s12 = s1.substr(i);
            string s21 = s2.substr(0,i);
            string s22 = s2.substr(i);
            if(isScramble(s11,s21) && isScramble(s12,s22)) return true;
            s21 = s2.substr(s2.size()-i,i);
            s22 = s2.substr(0,s2.size()-i);
            if(isScramble(s11,s21) && isScramble(s12,s22)) return true;
        }
        return false;
    }//87

转载于:https://www.cnblogs.com/2Bthebest1/p/10834413.html

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode87. 扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：如果字符串的长度为 1 ，算法停止如果字符串的长度 > 1 ，执行下述步骤：在一个随机下标处将字符串分

分手后的思念是犯贱/ 2023年01月13日 08:52/ 0 赞/ 108 阅读

相关 LeetCode 86分割链表&87扰乱字符串

> 微信搜一搜：`bigsai` 专注于Java、数据结构与算法，一起进大厂不迷路！ > 算法文章题解全部收录在github仓库[bigsai-algorithm][],求

快来打我*/ 2022年12月29日 00:13/ 0 赞/ 127 阅读

相关 Leetcode No.21

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

秒速五厘米/ 2022年11月19日 07:50/ 0 赞/ 170 阅读

相关 Leetcode No.111

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

小咪咪/ 2022年10月31日 00:48/ 0 赞/ 175 阅读

相关 Leetcode No.94

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

布满荆棘的人生/ 2022年10月29日 12:22/ 0 赞/ 170 阅读

相关 Leetcode No.53

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

痛定思痛。/ 2022年10月26日 04:57/ 0 赞/ 164 阅读

相关 LeetCode87——Scramble String

LeetCode87——Scramble String 原题 > Given a string s1, we may represent it as a binar

墨蓝/ 2022年08月20日 13:29/ 0 赞/ 117 阅读

相关【LeetCode】87. Scramble String解法及注释

87. Scramble String Total Accepted: 44881 Total Submissions: 170059 Difficulty: Hard G

素颜马尾好姑娘i/ 2022年07月27日 11:50/ 0 赞/ 156 阅读

相关【Leetcode】87. Scramble String（DFS）（字符串）

Given a string s1, we may represent it as a binary tree by partitioning it to two non-em

男娘i/ 2022年02月23日 14:40/ 0 赞/ 186 阅读

相关 Leetcode No.87 ***

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。示例 1: 输入: s1 = "great", s2 = "rgeat"

ゞ浴缸里的玫瑰/ 2021年12月01日 09:59/ 0 赞/ 240 阅读