首页 » 编程之美 » 正文

[leetcode_87]Scramble String

这个题自己独立做出来的,还是很高兴的,前面有两个题把我打击得都快没信心了。一个数据过不了,一个方法想不到。
最开始想暴力,枚举每个间歇,只要满足左边和右边的字符串经过排序相等即可。
把这个思想,模拟一下,去找出现左边和左边相等的串即可。

int cmp(char a,char b) {
    return a < b;
}
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.length() != s2.length())return false;
        string s1t = s1;
        string s2t = s2;
        sort(s1.begin(),s1.end(),cmp);
        sort(s2.begin(),s2.end(),cmp);
        if(s1 != s2)return false;
        return checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
    }
private:
    bool checkIs(string s1,string s2) {
        if(s1.length() <= 0)return true;
        if(s1.length() == 1) {
            if(s1[0] == s2[0])return true;
            else return false;
        }
        int i = 0;
        while(i < s1.length()) {
            if(s2[i] != s1[0]) {
                i++;
                continue;
            }<br />
            string s1b(s1,1,i);
            string s2b(s2,0,i);
            sort(s1b.begin(),s1b.end(),cmp);
            sort(s2b.begin(),s2b.end(),cmp);
            if(s1b != s2b) {
                i++;
                continue;
            }
            else
                break;
        }
        if(i == s1.length())return false;
        if(i == s1.length()-1) {
            string s1t = string(s1,1,i);
            string s2t = string(s2,0,i);
            return checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
        }
        string s1e(s1,i+1);
        string s2e(s2,i+1);
        sort(s1e.begin(),s1e.end(),cmp);
        sort(s2e.begin(),s2e.end(),cmp);
        if(s1e != s2e)return false;
        string s1t = string(s1,1,i);
        string s2t = string(s2,0,i);
        bool flag1 = checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend())); 
        s1t = string(s1,i+1);
        s2t = string(s2,i+1);
        bool flag2 = checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
        return flag1 &amp;&amp; flag2;
    }
};

发表评论