LeetCode Scramble String

LeetCode解題之Scramble String

原題

一個字符串可以拆分成兩個都不為空的子字符串，而子字符串（長度大於等於二）也可以不斷這樣拆分下去，現在可以任意交換拆分出來兩部分的位置來改變字符串中字符的順序。判斷兩個字符能否通過這種方式相互轉換。

注：這道題比較難用語言描述，可以參見原題中的圖例

原題請點 這裡

注意點：

例子：

輸入: s1 = “rgtae”, s2 = “great”

輸出: True (“rgtae”->”grtae”->”greta”->”great”)

解題思路

對三維動態規劃還不是很熟練，偷懶用了最簡單的遞歸方式，以後會補上動態規劃解法。要判斷兩個字符S和T能否轉化，先把它們各自分為兩部分，如果S的前半部分和T的前半部分能轉換，它們的後半部分也能轉換，說明它們就能轉換；但也有可能S的前半部分和後半部分是在最後一交換中轉換回來的，也就是S的前半部分和T的後半部分能夠轉換，而T的前半部分和S的後半部分能夠轉換同樣能夠達到目的。還可以在我代碼的基礎上再做一些優化，如提前判斷兩個要轉化的字符串中各字符的數目是否相等來進行剪枝，來減少沒有用的遞歸。經過剪枝的遞歸算法的運行速度還是很快的。

AC源碼

from collections import defaultdict


class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if s1 == s2:
            return True
        count1 = defaultdict(int)
        count2 = defaultdict(int)
        for e1, e2 in zip(s1, s2):
            count1[e1] += 1
            count2[e2] += 1
        if count1 != count2:
            return False
        for i in range(1, len(s1)):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) \
                    or self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:len(s2) - i]):
                return True
        return False