本文主要是介绍leetcode 87 Scramble String(c++,beat 80%~100%)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解
符号：
- S_(i-j):表示字符串s下标从i到j的字串。
思路
其实没什么规律，就是暴力枚举交换轴，然后每次有交换与不交换两种情况，递归判断是否可行。唯一剪枝就是假如S1_(i,j)=S2_(k,l)，则他们所包含的字母的集合是相同的，如果不同，则不用再继续递归下去。
代码
class Solution {
public:int *sum1,*sum2;bool dfs(int l1,int r1,int l2,int r2,string &s1,string &s2){if(sum1[r1+1]-sum1[l1]!=sum2[r2+1]-sum2[l2]) return false;if(l1==r1){return s1[l1]==s2[l2];}int res =0;for(int i=0;i<r1-l1+1-1;i++){res|=dfs(l1,l1+i,l2,l2+i,s1,s2)&&dfs(l1+i+1,r1,l2+i+1,r2,s1,s2);if(res) break;res|=dfs(l1,l1+i,r2-i,r2,s1,s2)&&dfs(l1+i+1,r1,l2,r2-i-1,s1,s2);if(res) break;}return res;}bool isScramble(string s1, string s2) {if(s1.size()==0) return true;sum1= new int[s1.size()+1];sum2 = new int[s2.size()+1];sum1[0]=sum2[0]=0; for(int i=0;i< s1.size();i++){sum1[i+1]=(sum1[i]+((s1[i]*s1[i])^123563));sum2[i+1]=(sum2[i]+((s2[i]*s2[i])^123563));}return dfs(0,s1.size()-1,0,s2.size()-1,s1,s2);return false;}
};
这篇关于leetcode 87 Scramble String(c++,beat 80%~100%)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
