Giả sử chúng ta có một chuỗi các dấu ngoặc vuông (tròn, xoăn và vuông), chúng ta phải kiểm tra xem các dấu ngoặc vuông có cân đối (đúng dạng) hay không.
Vì vậy, nếu đầu vào là s ="([() ()] {[]}) ()", thì đầu ra sẽ là True
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- stack:=một danh sách mới
- d:=một bản đồ băm với các cặp khóa-giá trị ('}', '{'), (')', '('), (']', '[')
- đối với mỗi ký tự c trong s, thực hiện
- nếu c là bất kỳ một trong số '}])', thì
- nếu ngăn xếp trống hoặc đầu ngăn xếp không giống với d [c], thì
- trả về Sai
- bật ra từ ngăn xếp
- nếu ngăn xếp trống hoặc đầu ngăn xếp không giống với d [c], thì
- nếu không,
- đẩy c vào ngăn xếp
- nếu c là bất kỳ một trong số '}])', thì
- trả về true khi ngăn xếp trống, ngược lại là false
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):
stack = []
d = {'}': '{',')': '(',']': '['}
for c in s:
if c in '}])':
if not stack or stack[-1] != d[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
ob = Solution()
print(ob.solve("([()()]{[]})()")) Đầu vào
"([()()]{[]})()" Đầu ra
True