สมมติว่ามีสตริง s ประกอบด้วยวงเล็บ '(', ')' และตัวอักษรภาษาอังกฤษพิมพ์เล็ก ต้องลบวงเล็บน้อยที่สุดเพื่อให้สตริงที่เหลือเป็นวงเล็บที่ถูกต้อง (valid parentheses) วงเล็บถูกต้องหมายถึง:
- สตริงว่างหรือมีแต่ตัวอักษร
- เป็น
ABโดยA,Bถูกต้อง - เป็น
(A)โดยAถูกต้อง
ตัวอย่าง: s = "m)n(o)p" ผลลัพธ์ "mn(o)p"
วิธีแก้ปัญหา
stack := [],indexes := set(),i := 0- วน
cในs:- ถ้า
c == '(':stack.append(i) - ถ้า
c == ')':- ถ้า
stackว่าง:indexes.add(i) - มิฉะนั้น:
stack.pop()
- ถ้า
i += 1
- ถ้า
indexes := indexes.union(stack)- สร้าง
retโดยข้ามดัชนีในindexes - คืนค่า
ret
ตัวอย่างโค้ด
def solve(s):
stack = []
indexes = set()
i = 0
for c in s:
if c == '(':
stack.append(i)
elif c == ')':
if len(stack) == 0:
indexes.add(i)
else:
stack.pop()
i += 1
ret = ''
indexes = indexes.union(stack)
for i in range(len(s)):
if i not in indexes:
ret += s[i]
return ret
s = "m)n(o)p"
print(solve(s))
อินพุต
"m)n(o)p"
เอาต์พุต
mn(o)p
