Leedcode

87. Scramble String

2018-06-09  本文已影响0人  凉拌姨妈好吃

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

  1. 如果两个字符串的各个字符数量都不相等,直接返回false(在这里判断各字符是否相等,有点像桶排序,将所有字符都减去‘a’字符,这样就可以得出各个字符的索引,通过索引存储数据就可以判断字符数量了)
  2. 我们从字符串的最左边的字符开始截取,然后比较字符串AB截取后的子串
  3. 我们有两种比较方式:
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;
            
    }
    
};
上一篇 下一篇

猜你喜欢

热点阅读