สมมติว่าเรามีสตริง s ที่มีวงเล็บ '(' , ')' และอักขระภาษาอังกฤษตัวพิมพ์เล็ก เราต้องลบจำนวนวงเล็บขั้นต่ำ ( '(' หรือ ')' จากตำแหน่งใดๆ ) เพื่อให้สตริงที่เป็นผลลัพธ์มีความถูกต้องและต้องส่งคืนสตริงที่ถูกต้องในที่สุด สตริงวงเล็บจะใช้ได้เมื่อเป็นไปตามเกณฑ์เหล่านี้ทั้งหมด -
-
สตริงว่างเปล่าและมีอักขระตัวพิมพ์เล็กเท่านั้น หรือ
-
สตริงสามารถเขียนเป็น AB (A ต่อกับ B) โดยที่ A และ B เป็นสตริงที่ถูกต้อง หรือ
-
สตริงสามารถเขียนเป็นรูปแบบของ (A) โดยที่ A เป็นสตริงที่ถูกต้อง
ดังนั้น หากอินพุตเป็น s ="m)n(o)p" ผลลัพธ์จะเป็น "mn(o)p"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
stack :=รายการใหม่
-
ดัชนี :=ชุดใหม่
-
ผม :=0
-
สำหรับแต่ละ c ใน s ทำ
-
ถ้า c เหมือนกับ '(' แล้ว
-
ดันฉันเข้ากอง
-
-
มิฉะนั้นเมื่อ c เหมือนกับ ')' แล้ว
-
ถ้าขนาดของ stack เท่ากับ 0 แล้ว
-
แทรก i ลงในดัชนี
-
-
มิฉะนั้น
-
ป๊อปจากสแต็ก
-
-
ผม :=ผม + 1
-
-
-
ret :=สตริงว่าง
-
ดัชนี :=เก็บองค์ประกอบทั้งหมดไว้ในดัชนี
-
สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ
-
ถ้าฉันไม่ได้อยู่ในดัชนีแล้ว
-
ret :=ret + s[i]
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
