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)。
❓
延伸问答
如何判断一个括号字符串是否有效？
一个括号字符串有效的条件包括：空字符串、可以写成AB（A与B的连接），或可以写成(A)（A是有效字符串）。
如何计算使括号字符串有效所需的最少插入次数？
通过遍历字符串，使用balance记录括号平衡，additions记录需要插入的括号数，最终返回additions的值。
在遍历括号字符串时，如何处理多余的闭括号？
当balance为负时，表示闭括号多于开括号，需要增加一个开括号，additions加1并重置balance为0。
如果字符串以多个开括号开始，如何计算插入次数？
如果遍历结束后balance大于0，表示有未匹配的开括号，将其加到additions中。
该算法的时间复杂度和空间复杂度是多少？
该算法的时间复杂度为O(n)，空间复杂度为O(1)。
给定字符串'())'，需要插入多少个括号才能使其有效？
需要插入1个括号才能使字符串'())'有效。
➡️
