Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出两个字符串,可以进行任意多次操作,每次将字符串切分成两个,选择对调两个子串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 = {}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理