87. Scramble String

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

  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;
            
    }
    
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容