python实现leetcode之87. 扰乱字符串

解题思路

缓存
分情况处理：
1.两个字符串相等，直接为True
2.两个字符串组成的元组作为key查缓存，如果命中直接返回
3.从前起头并进扫描两个字符串，如果他们在中间并且包含相同数量的字符计数，就作为一个分治点，检查两个子串，如果成功就返回
4.第一个从头扫，第二个从尾扫，其他做法与3一致
以上都处理过，返回False
每一步返回之前记得缓存一下

87. 扰乱字符串

代码

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        return cached_is(s1, s2, {})


def cached_is(s1, s2, cache):
    if s1 == s2: return True
    key = (s1, s2)
    if key in cache: return cache[key]

    id_1 = [0] * 26
    id_2 = [0] * 26
    for i, (c1, c2) in enumerate(zip(s1, s2)):
        id_1[ord(c1)-ord('a')] += 1
        id_2[ord(c2)-ord('a')] += 1
        if id_1 == id_2 and i != len(s1)-1:
            # 索引i及其之前的部分，两个字符串拥有相同的字符计数
            if cached_is(s1[:i+1], s2[:i+1], cache) and cached_is(s1[i+1:], s2[i+1:], cache):
                cache[key] = True
                return cache[key]
    # 颠倒
    rid_1 = [0] * 26
    rid_2 = [0] * 26
    for i in range(len(s1)):
        i2 = len(s2)-1-i
        c1, c2 = s1[i], s2[i2]
        rid_1[ord(c1)-ord('a')] += 1
        rid_2[ord(c2)-ord('a')] += 1
        if id_1 == id_2 and i != len(s1)-1:
            # s1[0...i]与s2[-1-i...length]具有相同的字符计数
            if cached_is(s1[:i+1], s2[i2:], cache) and cached_is(s1[i+1:], s2[:i2], cache):
                cache[key] = True
                return cache[key]
    cache[key] = False
    return False