題目描述
Given a strings1, we may represent it as a binary tree by? partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1="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 stringss1ands2of the same length,? determine ifs2is a scrambled string ofs1.
這道題定義了一種爬行字符串，就是說(shuō)假如把一個(gè)字符串當(dāng)做一個(gè)二叉樹(shù)的根，然后它的非空子字符串是它的子節(jié)點(diǎn)，然后交換某個(gè)子字符串的兩個(gè)子節(jié)點(diǎn)，重新爬行回去形成一個(gè)新的字符串，這個(gè)新字符串和原來(lái)的字符串互為爬行字符串。這道題可以用遞歸Recursion或是動(dòng)態(tài)規(guī)劃Dynamic Programming來(lái)做，我們先來(lái)看遞歸的解法，參見(jiàn)網(wǎng)友uniEagle的博客，簡(jiǎn)單的說(shuō)，就是s1和s2是scramble的話，那么必然存在一個(gè)在s1上的長(zhǎng)度l1，將s1分成s11和s12兩段，同樣有s21和s22.那么要么s11和s21是scramble的并且s12和s22是scramble的；要么s11和s22是scramble的并且s12和s21是scramble的。就拿題目中的例子 rgeat 和 great 來(lái)說(shuō)，rgeat 可分成 rg 和 eat 兩段， great 可分成 gr 和 eat 兩段，rg 和 gr 是scrambled的， eat 和 eat 當(dāng)然是scrambled。
題意在于判斷一個(gè)字符串是否為另一個(gè)字符串“亂序”得到，這種亂序采用的方式是將一個(gè)字符串從某個(gè)位置“割開(kāi)”，形成兩個(gè)子串，然后對(duì)兩個(gè)子串進(jìn)行同樣的“割開(kāi)”操作，直到到達(dá)葉子節(jié)點(diǎn)，無(wú)法再分割。然后對(duì)非葉子節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)進(jìn)行交換，最后重新從左至右組合形成新的字符串，由于這個(gè)過(guò)程中存在字符位置的變化，因此，原來(lái)的字符串順序可能會(huì)被打亂，當(dāng)然也可能沒(méi)有（同一個(gè)非葉子節(jié)點(diǎn)的左右孩子交換0次或偶數(shù)次，就無(wú)變化）。
