DEV Community
·
2116. 检查括号字符串是否有效
💡
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定一个括号字符串和一个锁定字符串，判断是否可以将括号字符串变为有效的括号字符串。有效条件包括字符串长度为偶数，且在遍历过程中闭括号不能超过开括号。通过从左到右和从右到左两次遍历检查括号的平衡性，时间复杂度为O(n)。
🎯
关键要点
-
括号字符串是由'('和')'组成的非空字符串，只有在特定条件下才有效。
-
有效条件包括字符串长度为偶数，且在遍历过程中闭括号不能超过开括号。
-
给定一个括号字符串s和一个锁定字符串locked，locked为二进制字符串，'1'表示该位置不可更改，'0'表示可更改。
-
如果字符串长度为奇数，立即返回false，因为有效的括号字符串必须是偶数长度。
-
遍历字符串时，跟踪开括号和闭括号的数量，若闭括号超过开括号，则返回false。
-
需要处理锁定位置和解锁位置，解锁位置可以更改字符，锁定位置则不能。
-
算法步骤包括：检查字符串长度是否为奇数，左到右遍历跟踪括号平衡，右到左遍历处理未匹配的开括号。
-
时间复杂度为O(n)，适合输入大小限制。
➡️
