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