Posted on 2023-03-30 16:51
Uriel 閱讀(60)
評論(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 = {}