问题描述

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
问题描述详见LeetCode页面。

问题分析

将s1切割成两部分，将s2也切割成相同长度的两部分（有两种切割方法），判断s2的子串是否为s1的scrambled string，递归解题。
hint：在递归前先判断一下两个字符串的组成字母是否一致，不一致直接返回False。

AC代码

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        n = len(s1)
        if n == 1:
            return s1 == s2
        dic1 = {}
        for c in s1:
            if dic1.has_key(c):
                dic1[c] += 1
            else:
                dic1[c] = 1
        for c in s2:
            if not dic1.has_key(c) or dic1[c] == 0:
                return False
            dic1[c] -= 1
        for i in range(1, n):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) or self.isScramble(s1[:i], s2[n-i:]) and self.isScramble(s1[i:], s2[:n-i]):
                return True
        return False

Runtime: 56 ms, which beats 100.00% of Python submissions. （有偶然性但是我不想再交啦23333）