Giả sử, chúng ta có một chuỗi chữ thường s chứa các chữ cái và dấu ngoặc đơn "(" và ")". Chúng ta phải đảo ngược mọi chuỗi nằm trong dấu ngoặc đơn theo cách đệ quy và trả về chuỗi kết quả.
Vì vậy, nếu đầu vào là s ="back (aps) ce", thì đầu ra sẽ là "backspace".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm trav (). Thao tác này sẽ lấy s, dir, start, close:=close, ans:=ans
-
end:="(" nếu dir giống −1, ngược lại ")"
-
khác:="(" nếu kết thúc giống như ")", nếu không thì ")"
-
trong khi start
-
nếu s [start] giống với s [start] khác, thì
-
trav (s, -dir, close [other, start] - dir)
-
start:=close [other, start] + dir
-
-
nếu không,
-
chèn s [start] vào cuối ans
-
start:=start + dir
-
-
-
-
Từ chức năng chính, thực hiện như sau -
-
ans:=một danh sách mới
-
close:=một bản đồ mới chứa các khóa “)” và “(” ban đầu các giá trị là hai bản đồ trống
-
stack:=một danh sách mới
-
đối với mỗi chỉ số I và giá trị c tính bằng s, thực hiện
-
nếu c giống với "(", thì
-
đẩy tôi vào ngăn xếp
-
-
ngược lại khi c giống với ")" thì
-
o:=trên cùng của ngăn xếp, sau đó bật ra từ ngăn xếp
-
đóng [")", i]:=o
-
đóng ["(", o]:=i
-
-
-
trav (s, 1, 0)
-
trả về ans được nối với chuỗi trống
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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")) Đầu vào
"back(aps)ce"
Đầu ra
backspace