資料結構
網路
關係型資料庫管理系統
作業系統
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
更新於： 2020-12-26
436 次瀏覽
廣告