【LeetCode】*0087 扰乱字符串

https://leetcode-cn.com/problems/scramble-string/

import functools
class Solution:
    @functools.lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        if sorted(s1) != sorted(s2):
            return False
        for i in range(1, len(s1)):
            if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):
                return True
            if self.isScramble(s1[:i],s2[-i:]) and self.isScramble(s1[i:],s2[:-i]):
                return True
        return False

思路：这道题第一眼看上去应该是dp，从窗口大小1到n，判断翻转相同还是不翻转相同还是怎么都不相同（这个思路考虑少了，但是总的来说确实是这个思路），后来我突然意识到这道题可以不用dp那么麻烦，于是就有了下面的代码：

# -*- coding:utf-8 -*-

from collections import deque
class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        n = len(s1)
        queue = deque()
        # 处理连续重复字符
        latter_idx = 0
        for i in range(1, n):
            if s1[i] != s1[i - 1]:
                break
            latter_idx = i
        s1 = s1[latter_idx:]
        for i in range(n):
            if len(s2) == n and s2[i] == s1[0]:
                for j in range(i, n - 1):
                    if s2[i] == s2[i + 1]:
                        s2 = s2[:j] + s2[j + 1:]
                    elif s2[i] != s2[i + 1]:
                        break
        if len(s1) != len(s2):
            return False
        n = len(s1)
        current_idx = 0
        # 判断
        while current_idx < n:
            # 寻找翻转位置
            same_idx = 0
            for j in range(current_idx, n):
                if s2[j] == s1[current_idx]:
                    same_idx = j + 1
                    break
                if j == n - 1:
                    return False
            # 入栈
            for k in range(current_idx, same_idx):
                queue.append(s1[k])
            # 比较出栈
            for k in range(current_idx, same_idx):
                if s2[k] == queue[-1]:
                    queue.pop()
                elif s2[k] == queue[0]:
                    queue.popleft()
                else:
                    return False
            current_idx = same_idx
            pass
        return True
        pass
if __name__ == '__main__':
    s1 = 'great'
    s2 = 'rgeat'
    s1 = 'abc'
    s2 = 'bca '
    print(Solution().isScramble(s1, s2))

上面的代码整体思路是：现在s2中找s1的0字符，然后判断这两个子串是不是相同的（这里的相同定义为正序倒序又一个相同即可，下同），如果是更新开始索引，继续从这个索引继续向后判断，十分类似树的前序遍历和中序遍历的那个找发。

写的时候就意识到这个算法的局限性在于对于前n个相同字符的（比如aab，前2个相同）有局限性，因此也在最开始写了处理办法，直接做一次查找，将aab变成ab（s2当然也做等价变化），但是提交的时候发现，我从最开始就少想了一种情况，就是究极无敌交换，不仅字符交换，子串也交换，就硬换。

这时候就应该不能投机取巧了，应该老老实实的进行递归查找或者进行dp，这道题dp并不比递归快（做缓存的递归）。