สมมติว่ามีสตริง s ที่มีวงเล็บสมดุล "(" และ ")" เราต้องแบ่งพวกมันออกเป็นจำนวนกลุ่มสมดุลสูงสุด
เช่น ถ้าอินพุตคือ "(()())()(())" ผลลัพธ์จะเป็น ['(()())', '()', '(())']
ขั้นตอนการแก้ปัญหา
- temp := สตริงว่าง
- groups := รายการใหม่
- count := 0
- สำหรับแต่ละตัวอักษร b ใน s ทำ
- ถ้า count == 0 และ len(temp) > 0 ใส่ temp เข้า groups, temp := สตริงว่าง
- temp := temp + b
- ถ้า b == '(' count := count + 1 มิฉะนั้น count := count - 1
- ใส่ temp เข้า groups
- คืนค่า groups
ตัวอย่างโค้ด
class Solution:
def solve(self, s):
temp = ''
groups = []
count = 0
for b in s:
if count == 0 and len(temp) > 0:
groups.append(temp)
temp = ''
temp += b
if b == '(':
count += 1
else:
count -= 1
groups.append(temp)
return groups
s = "(()())()(())"
ob = Solution()
print(ob.solve(s))
อินพุต
"(()())()(())"
เอาต์พุต
['(()())', '()', '(())']
