題目連結：
題目意譯：
我們可以藉由以下演算法來將字串 s 打亂並得到一個字串 t：
1. 如果字串的長度為 1，則停止。
2. 如果字串的長度 > 1，則做以下事情：
以一個隨機索引值為準將字串分切成兩個非空子字串，即如果此時字串為 s，則將其分切成 x 和 y 使得 s = x + y。
隨機決定要不要交換兩個子字串的順序或是維持不變，即經過此步驟後，s 可能變成 x + y 或是 y + x。
分別對於 x 和 y 這兩個子字串各自從步驟 1. 開始遞迴。
給定兩個相同長度的字串 s1 和 s2。如果 s2 是 s1 打亂後的字串，則回傳真（True）；反之，則回傳假（False）。
限制：
s1.length == s2.length
1 ≦ s1.length ≦ 30
s1 和 s2 由小寫英文字母組成。
範例測資：
範例 1：
輸入： s1 = "great", s2 = "rgeat"
輸出： true
解釋： 在 s1 其中一個可能的情況為：
"great" --> "gr/eat" // 在隨機索引值切開。
"gr/eat" --> "gr/eat" // 隨機決定出不交換兩子字串，因此維持原狀。
"gr/eat" --> "g/r / e/at" // 對兩子字串遞迴並執行同一個演算法。對每個在隨機索引值來切開。
"g/r / e/at" --> "r/g / e/at" // 隨機決定出交換第一個子字串的結果，並將第二個子字串維持原狀。
"r/g / e/at" --> "r/g / e/ a/t" // 一樣，遞迴套用同個演算法，將 "at" 切成 "a/t"。
"r/g / e/ a/t" --> "r/g / e/ a/t" // 隨機決定出將兩個子字串維持原狀。
演算法到此結束，而結果字串為 "rgeat"，而其為 s2。
上述情況將會使 s1 打亂成 s2，因此我們回傳真。
範例 2：
輸入： s1 = "abcde", s2 = "caebd"
輸出： false
範例 3：
輸入： s1 = "a", s2 = "a"
輸出： true
解題思維：
如同在這題提過的動態規劃（Dynamic Programming，DP）之精神之一——如果你不知道要做哪個子問題，那就全做吧！
以 s1 = "abc" 、 s2 = "cab" 為例：
一開始在看到 s1 時，我們會有兩種可能的分切法，"a" + "bc" 和 "ab" + "c"。
接著我們可以選擇交換或不交換，而這會有以下四種可能的情況：
"a" + "bc"、
"bc" + "a"、
"ab" + "c"、
"c" + "ab"
而這將產生八個子問題（上述每種情況會各自有兩個）：
s1 中的 "a" 對 s2 中 "c" + s1 中的 "bc" 對 s2 中 "ab"、
s1 中的 "bc" 對 s2 中 "ca" + s1 中的 "a" 對 s2 中 "b"、
s1 中的 "ab" 對 s2 中 "ca" + s1 中的 "c" 對 s2 中 "b"、
s1 中的 "c" 對 s2 中 "c" + s1 中的 "ab" 對 s2 中 "ab"
那要怎麼表示這些子問題呢？
方法一：四個索引值 l1, r1, l2, r2，用來代表 s1[l1 …… r1]（這代表 s1 中第 l1（含）～ r1（含）個字元）這個子字串對上 s2[l2 …… r2] 這個子字串的子問題。
方法二：跟方法一類似，只是因為兩者子字串長度會是一樣的，因此可以只用三個變數表示一個子問題。分別是 l1 、 l2 和 L，其中 l1 和 l2 依序是 s1 、 s2 各自的子字串「開頭」，而 L 則是此子問題中兩字串的「長度」。
方法三：直接把 s1 和 s2 串接在一起。這只適用於雜湊表（Hash Table）或平衡樹以鍵值（Key）來儲存，不像方法一和方法二可以用多維陣列直接儲存。
知道怎麼表示子問題之後，便可以來開始觀察遞迴式。由於範例程式碼是用方法三的方式儲存，因此以下根據方法三表示：
定義一個雜湊表 D，其中 D[s] 代表著在 s1 = s[0 …… h - 1] 、 s2 = s[h …… n] 的情況下，s2 是否為 s1 打亂後的字串。當中 n 為 s 之長度，h 為 n 的一半（注意，n 必為偶數）。可以看到其遞迴式為：
當 h == 1 且 s1 == s2，則 D[s] = true；
當 h == 1 且 s1 != s2，則 D[s] = false；
（上述兩者為停止條件，代表著題目定義的演算法之「終點」。此時只需要看兩者是否相同即可。）
當 h != 1 且 s1 的字元與 s2 的字元不一致，則 D[s] = false。
（上面這條代表著另一個基本條件，如果兩者字元無法一一對應，則必定不可能從 s1 打亂變成 s2）
以上皆非，則 D[s] = true 若且唯若存在著一索引值 i（0 ≦ i < h）使得：
D[s1[0 …… i] + s2[0 …… i]]
和
D[s1[i + 1 …… h - 1] + s2[i + 1 …… h - 1]]
都為 true，或是
D[s1[i + 1 …… h - 1] + s2[0 …… h - i - 2]]
和
D[s1[0 …… i] + s2[h - i - 1 …… h - 1]]
都為 true。
（這邊就代表著所有要做的子問題了，就單純窮舉所有分切點（即索引值 i）然後各自做一次不交換和交換子字串。）
而要檢查兩字串字元一不一致很簡單，用兩個陣列統計兩者各自的字元出現次數然後一一比對即可（甚至可以只用單一一個陣列）。
接著從最一開始給定的 s1 和 s2，遞迴求 D[s1 + s2] 的結果即可。值得注意的是，子問題可能會重複。因此請記得善用先前求到的結果，不要再次遞迴（只會浪費時間而已）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
