[leetcode] Scramble String @python
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.
字符串的好題。題干解釋的非常復雜，一下讓人不知所措了。
這道題到底是什麼意思呢？最終的結果是把一個字符串中字母的順序打亂了，讓你判斷一個字符串能不能由另一個字符串打亂得到。那打亂這個過程是怎麼做的呢，很簡單，給你一個字符串，你必須先找一個點把它砍成兩半，你可以通過交換這兩半的順序來打亂源字符串的順序，也就是在兩半中的字符與另一半中所有字符的相對順序是統一的。對於每一半，都可以重復上面的過程。
那想一下，怎麼知道打斷的那個點在哪呢？窮舉。怎麼知道打斷之後有沒有做交換操作呢？兩種情況遞歸，有一條走的通就可以了。還有個問題，兩個字符串中包含的字符一定是完全一樣的，怎樣確定這一點呢？最暴力的方式，新開兩個字符串，排序，判斷這兩個新的相不相等。
比如： "abcd", "bdac" are not scramble string
代碼：
復制代碼
class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if s1==s2: return True
if sorted(s1) != sorted(s2): return False # "abcd", "bdac" are not scramble string
length=len(s1)
for i in range(1,length):
if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]): return True
if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]): return True
return False
