Leetcode Scramble String 搜尋亂序字元

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = 

"great"

:

great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
      

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node 

"gr"

 and swap its two children, it produces a scrambled string 

"rgeat"

.

rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
      

We say that 

"rgeat"

 is a scrambled string of 

"great"

.

Similarly, if we continue to swap the children of nodes 

"eat"

 and 

"at"

, it produces a scrambled string 

"rgtae"

.

rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
      

We say that 

"rgtae"

 is a scrambled string of 

"great"

.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

好困難的一題，自己研究出來了，不過很難确定是什麼判斷條件結束，是以耽誤了不少時間。

一看樣子就知道使用遞歸無疑了。

主要卡我時間最長的是遞歸的時候需要交叉遞歸的，因為根的兩個子樹以及下面的所有子樹都是可以調換的。

思路：

1 檢查長度是否一樣，不一樣就傳回false

2 檢查目前兩個字元是否為亂序，但是所有字元數相等，檢查有兩個方法： 1） 使用hash表  2）操作字元string排序比較；這裡計算就相當于剪枝了，沒有這一步會逾時的。

3 逐個字元分隔成兩個子樹，然後遞歸，注意s1和s2是可以交叉遞歸的。

好像字元串和一般原始資料一樣快，直接操作字元串string的速度很快，比如本題的直接操作字元串的速度也很快。

不過注意如果使用fixedTable為256，即假設為256個ascII碼，那麼就會比假設為26個小寫字元的速度慢上一倍。是以要搞清楚題目要求，根據題目設定hash表

本題也可以使用三維動态規劃法，leetcode上有幾個列子都是使用動态規劃法的。

LeetCode上的例子一般都很好，但是這次例外了，這些動态規劃法的例子并不好，因為本題使用動态規劃法增加了空間複雜度，甚至時間複雜度，而且實際運作時間比遞歸剪枝法慢。

下面是使用hash表，利用四點定位遞歸的程式。

vector<int> fixedTable;
	vector<int> countTable;
	bool isScramble2(string s1, string s2) 
	{
		if (s1.length() != s2.length()) return false;
		return scrambleRecur(s1,s2,0,s1.length()-1,0,s2.length()-1);
	}

	bool scrambleRecur(string &s1, string &s2, 
		int begin1, int back1, int begin2, int back2)
	{
		if (begin1 > back1 || (begin1==back1 && s1[begin1]==s2[begin2])) 
			return true;

		fixedTable.clear(); fixedTable.resize(26);
		countTable.clear(); countTable.resize(26);

		//有重複的時候需要特殊處理
		for (int i = begin1; i <= back1; i++)		//例如："abab", "bbaa"
		{
			fixedTable[s1[i]-'a']++;
		}

		for (int i = begin2; i <= back2; i++)
		{
			countTable[s2[i]-'a']++;
			if (fixedTable[s2[i]-'a'] < countTable[s2[i]-'a']) return false;
		}

		//注意：不要寫成i<=back-begin，因為遞歸最重要的原則：子遞歸必定要比原問題要小，否則就會無限遞歸，記憶體溢出了。
		for (int i = 0; i < back1-begin1; i++)
		{
			if (scrambleRecur(s1,s2,begin1,begin1+i,begin2, begin2+i)
				&&scrambleRecur(s1,s2,begin1+i+1,back1,begin2+i+1,back2)
				||scrambleRecur(s1,s2,begin1,begin1+i, back2-i,back2)
				&&scrambleRecur(s1,s2,begin1+i+1,back1,begin2,back2-i-1))
				return true;
		}
		return false;
	}
           

//2014-2-14 update
	bool isScramble(string s1, string s2) 
	{
		if (s1.length() != s2.length()) return false;
		if (s1 == s2) return true;
		
		int A[26] = {0};
		for(auto x:s1)
			A[x-'a']++;
		for(auto x:s2)
			A[x-'a']--;
		for(auto x:A)
			if(x != 0) return false;
		
		if (s1.length() < 4) return true;

		for (int i = 1; i < s1.length(); i++)
		{
			if (isScramble(s1.substr(0, i), s2.substr(0, i)) && 
				isScramble(s1.substr(i), s2.substr(i))
				|| isScramble(s1.substr(0, i), s2.substr(s2.length()-i)) &&
				isScramble(s1.substr(i), s2.substr(0,s2.length()-i)))
				return true;
		}
		return false;//注意：别忘了最後傳回
	}