美文网首页Leedcode
87. Scramble String

87. Scramble String

作者: 凉拌姨妈好吃 | 来源:发表于2018-06-09 15:54 被阅读0次

具体链接戳这
千万不要以为它是均等分!!!!!!
解题思路:

  1. 如果两个字符串的各个字符数量都不相等,直接返回false(在这里判断各字符是否相等,有点像桶排序,将所有字符都减去‘a’字符,这样就可以得出各个字符的索引,通过索引存储数据就可以判断字符数量了)
  2. 我们从字符串的最左边的字符开始截取,然后比较字符串AB截取后的子串
  3. 我们有两种比较方式:
  • 字符串A的前部分与字符串B的前部分比较,后部分与后部分比较
  • 字符串A的前部分与字符串B的后部分比较
class Solution {
public:
    bool isScramble(string s1, string s2) {

        if(s1==s2)
            return true;
            
        int count[26] = {0};
        for(int i=0; i<s1.size(); i++)
        {
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }
        
        for(int i=0; i<26; i++)
        {
            if(count[i]!=0)
                return false;
        }
        
        for(int i=1; i<=s1.size()-1; i++)
        {
            if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
                return true;
        }
        return false;
            
    }
    
};

相关文章

  • 10.3 - hard总结2

    87. Scramble String: 区间dp加上memory search97. Interleaving ...

  • 87. Scramble String

    具体链接戳这千万不要以为它是均等分!!!!!!解题思路: 如果两个字符串的各个字符数量都不相等,直接返回false...

  • 87. Scramble String

    Given a string s1, we may represent it as a binary tree b...

  • 87. Scramble String

    问题描述 Given two strings s1 and s2 of the same length, dete...

  • 2020-2-27 刷题记录

    今天,又只做了三道..... 0X00 leetcode 做了 3 道 leetcode 87. Scramble...

  • Scramble String

    题目Given a string s1, we may represent it as a binary tree...

  • 087 Scramble String

    Given a string s1, we may represent it as a binary tree b...

  • 87.Scramble String

    https://leetcode.com/problems/scramble-string/ 题意不是简单的rev...

  • Scramble String(未完待续)

    题目链接 题意 见题目链接 解答 因为二叉树是由字符串递归地分割生成的,所以能很自然地想到递归的解法。遍历 s1 ...

  • [LeetCode 87] Scramble String (H

    Given a string s1, we may represent it as a binary tree b...

网友评论

    本文标题:87. Scramble String

    本文链接:https://www.haomeiwen.com/subject/lfbteftx.html