Question: https://oj.leetcode.com/problems/scramble-string/
Question Name: Scramble String
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution: # @return a boolean def isScramble(self, s1, s2): if len(s1) != len(s2): return False if s1 == s2: return True # Check their char distribution before trying to swap it. charDis = {} for index in xrange(len(s1)): # Gather char distribution charDis[s1[index]] = charDis.get(s1[index], 0) + 1 charDis[s2[index]] = charDis.get(s2[index], 0) - 1 for index in xrange(len(s1)): # Check char distribution if charDis[s1[index]] != 0: return False # Try to divide the strings into two part, and may swap parts. for index in xrange(1, len(s1)): # Divided, but did not swap the parts if self.isScramble(s1[:index], s2[:index]) and self.isScramble(s1[index:], s2[index:]): return True # Divided, and swapped the parts if self.isScramble(s1[:index], s2[-index:]) and self.isScramble(s1[index:], s2[:len(s2)-index]): return True return False |