Posted on 2023-03-30 16:51
Uriel 阅读(22)
评论(0) 编辑 收藏 引用 所属分类:
递归 & 分治 、
闲来无事重切Leet Code
给出两个字符串，可以进行任意多次操作，每次将字符串切分成两个，选择对调两个子串or不对调，问字符串s1能否经过操作变为字符串
用了比较暴力的做法，穷举所有操作的可能性，用了Discussion中记录下已经暴力枚举过的结果，否则会TLE
https://leetcode.com/problems/scramble-string/solutions/3357439/easy-solutions-in-java-python-and-c-look-at-once-with-exaplanation
1 #1402
2 #Runtime: 222 ms (Beats 21.95%)
3 #Memory: 20.5 MB (Beats 7.32%)
4
5 class Solution(object):
6 def isScramble(self, s1, s2):
7 """
8 :type s1: str
9 :type s2: str
10 :rtype: bool
11 """
12 if len(s1) != len(s2):
13 return False
14 if s1 == s2:
15 return True
16 if len(s1) == 1:
17 return False
18 t = s1 + " " + s2
19 if t in self.solved:
20 return self.solved[t]
21 for i in range(1, len(s1)):
22 if self.isScramble(s1[0:i], s2[0:i]) and self.isScramble(s1[i:], s2[i:]):
23 self.solved[t] = True
24 return True
25 if self.isScramble(s1[0:i], s2[len(s1)-i:]) and self.isScramble(s1[i:], s2[0:len(s1)-i]):
26 self.solved[t] = True
27 return True
28 self.solved[t] = False
29 return False
30 solved = {}