数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中反转括号内子字符串的程序
假设我们有一个包含字母和括号“（”和“）”的小写字符串 s。我们必须以递归方式反转括号内包含的每个字符串，并返回结果字符串。
因此，如果输入类似于 s = "back(aps)ce"，则输出将为“backspace”。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 trav()。它将接收 s、dir、start、close:= close、ans:= ans 作为参数。
end := 如果 dir 与 -1 相同，则为 "("，否则为 ")"。
other := 如果 end 与 ")" 相同，则为 "("，否则为 ")"。
当 start < s 的大小，并且 s[start] 与 end 不相同，则执行以下操作：
如果 s[start] 与 other 相同，则执行以下操作：
trav(s, -dir, close[other, start] - dir)
start := close[other, start] + dir
否则，执行以下操作：
在 ans 的末尾插入 s[start]。
start := start + dir
从主函数执行以下操作：
ans := 一个新的列表。
close := 一个新的映射，包含键“)”和“(”，初始值为两个空映射。
stack := 一个新的列表。
对于 s 中的每个索引 I 和值 c，执行以下操作：
如果 c 与 "(" 相同，则执行以下操作：
将 i 推入 stack。
否则，当 c 与 ")" 相同，则执行以下操作：
o := stack 的顶部，然后从 stack 中弹出。
close[")", i] := o
close["(", o] := i
trav(s, 1, 0)
返回 ans 与空字符串连接的结果。
让我们看看以下实现，以更好地理解：
示例
class Solution:
def solve(self, s):
ans = []
close = {")": {}, "(": {}}
stack = []
for i, c in enumerate(s):
if c == "(":
stack.append(i)
elif c == ")":
o = stack.pop()
close[")"][i] = o
close["("][o] = i
def trav(s, dir, start, close=close, ans=ans):
end = "(" if dir == -1 else ")"
other = "(" if end == ")" else ")"
while start < len(s) and s[start] != end:
if s[start] == other:
trav(s, −dir, close[other][start] − dir)
start = close[other][start] + dir
else:
ans.append(s[start])
start += dir
trav(s, 1, 0)
return "".join(ans)
ob = Solution()
print(ob.solve("back(aps)ce"))输入
"back(aps)ce"
输出
backspace
436 次浏览
