DEV Community
·
921. 最少插入使括号有效
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定一个括号字符串，通过最少插入操作使其有效。遍历字符串时，用`balance`记录括号平衡，`additions`记录需要插入的括号数。当`balance`为负时，增加`additions`并重置`balance`。遍历结束后，若`balance`大于0，将其加到`additions`。时间复杂度为O(n)，空间复杂度为O(1)。
🎯
关键要点
- 括号字符串有效的条件包括：空字符串、可以写成AB（A与B的连接），或可以写成(A)（A是有效字符串）。
- 给定一个括号字符串s，通过插入括号使其有效，返回所需的最少操作次数。
- 使用变量balance记录当前括号的平衡，additions记录需要插入的括号数。
- 遍历字符串时，如果遇到'('，balance加1；遇到')'，balance减1。
- 当balance为负时，表示闭括号多于开括号，需要增加一个开括号，additions加1并重置balance为0。
- 遍历结束后，如果balance大于0，表示有未匹配的开括号，将其加到additions中。
- 该算法的时间复杂度为O(n)，空间复杂度为O(1)。
➡️
