首页 > 代码库 > 【leetcode】Scramble String

【leetcode】Scramble String

题目:给定两个串s1和s2,对s1串,我们可以将其分割成两部分,这两部分都不为空,而被分割成的两部分,又可以递归的进行分割,直到不能进行分割为止,也就是只有一个字符的时候,就不在分割了。问s2是否由s1的这种分割表示中,某步分割成的两部分交换得到的。这种交换可以在不同的分割点进行多次。

/*     s1
  |__________p____________|                  s1[0---p)---s1[0-p)
  0          |            len-1              s1[p-len)---s2[p-len)
             |                               
        s2   |                              
  |__________p____________|                 
  0                      len-1               
       s1
  |__________p____________|
  0                       len - 1
       s2   len-p                             s1[0---p)---s2[len-p, p)
  |__________|____________|                   s1[p-len)----s2[0,len - p)
  0          |____________|len - 1
                    |
                    p
*/ 
bool isScramble(string s1, string s2) {
	if(s1.size() == 0 && s2.size() == 0)
		return true;
	if(s1.size() != s2.size())
		return false;
	//pruning
	string temp1 = s1;
	string temp2 = s2;
	sort(temp1.begin(),temp1.end());
	sort(temp2.begin(),temp2.end());
	if(temp1 != temp2)
		return false;
	int len = s1.size();

	if(len == 1)
		return true;
	//try the every point
	for (int pt = 1; pt < len; ++pt)
	{
	   if(isScramble(s1.substr(0, pt),s2.substr(0, pt)) && 
		   isScramble(s1.substr(pt, len - pt),s2.substr(pt, len - pt)) ||
		   isScramble(s1.substr(0, pt),s2.substr(len - pt, pt)) &&
		   isScramble(s1.substr(pt, len - pt),s2.substr(0, len - pt)))
			return true;
	}
	return false;
}

居然在分割后,对左右部分的起始点弄不清了。