检查括号字符串是否有效

2116。检查括号字符串是否有效

难度：中等

主题：字符串、堆栈、贪婪

括号字符串是仅由“(”和“)”组成的非空字符串。满足以下任一条件即有效：

• 是()。
• 可以写为AB（A与B连接），其中A和B是有效的括号字符串。
• 可以写成 (A)，其中 A 是有效的括号字符串。

给你一个括号字符串 s 和一个锁定字符串，长度均为 n。 lock 是一个仅由“0”和“1”组成的二进制字符串。对于每个锁定的索引i，

• 如果locked[i]为“1”，您不能更改s[i]。
• 但是如果locked[i]是'0'，你可以将s[i]更改为'('或')'。

如果可以使 s 成为有效的括号字符串，则返回 true。否则，返回 false。

示例1：

• 输入： s = "))()))"，锁定 = "010100"
• 输出： true
• 解释：locked[1] == '1' 且locked[3] == '1'，因此我们无法更改s[1] 或s[3]。
  • 我们将 s[0] 和 s[4] 更改为 '('，同时保持 s[2] 和 s[5] 不变以使 s 有效。

示例2：

• 输入： s = "()()"，锁定 = "0000"
• 输出： true
• 说明：我们不需要进行任何更改，因为 s 已经有效。

示例 3：

• 输入： s = ")"，锁定 = "0"
• 输出： false
• 解释： 锁定允许我们更改 s[0]。
  • 将 s[0] 更改为“(”或“)”不会使 s 有效。

约束：

• n == s.length == 锁定.length
• 1 5
• s[i] 是 '(' 或 ')'。
• Locked[i] 为“0”或“1”。

提示：

1. 奇数长度的字符串是否有效？
2. 从左到右，如果遇到锁定的')'，则必须与其左侧锁定的'('或未锁定的索引平衡。如果都不存在，可以得出什么结论？如果都存在，哪个更适合使用？
3. 完成上述操作后，我们可能已经锁定了“(”的索引以及其他未锁定的索引。现在如何平衡锁定的“(”？如果无法平衡任何锁定的“(”怎么办？

解决方案：

我们可以一步步接近它，同时牢记锁定仓位的约束和行为。

要点：

1. 如果字符串的长度是奇数，我们可以立即返回 false，因为有效的括号字符串必须具有偶数长度（每个开头（需要一个结尾））。
2. 当我们迭代字符串时，我们需要跟踪左括号 (() 和右括号 ()) 的数量。如果在任何时候右括号的数量超过了左括号的数量，就不可能平衡字符串，我们返回 false。
3. 我们必须小心处理锁定（locked[i] == '1'）和解锁（locked[i] == '0'）的仓位。解锁的位置允许我们改变角色，但锁定的位置则不能。

算法：

• 第1步：检查字符串s的长度是否为奇数。如果是，立即返回 false。
• 第 2 步： 从左到右循环字符串以跟踪括号的平衡情况。
  • 使用计数器来跟踪左（和右）括号之间的平衡。
  • 如果在任何时候，右括号的数量超过左括号的数量，请检查锁定位置是否有足够的灵活性来平衡它。
  • 处理完整个字符串后，检查括号是否平衡，即是否没有剩余不匹配的左括号。

让我们用 PHP 实现这个解决方案：2116。检查括号字符串是否有效

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

解释：

1. 第一遍（从左到右）：

   • 我们迭代字符串并跟踪左括号的余额。每次遇到左括号（，我们都会增加开计数器。对于闭括号），我们会减少开计数器。
   • 如果当前字符被解锁（locked[i] == '0'），我们可以假设它是 ( 如果需要平衡括号。
   • 如果在任何时候开放计数器变为负数，则意味着我们的右括号多于左括号，并且我们返回 false。

2. 第二遍（从右到左）：

   • 我们反向执行类似的操作来处理可能位于字符串末尾的不匹配左括号的情况。
   • 这里我们用闭计数器跟踪右括号 ()) 并确保不存在不平衡的括号。

3. 边缘情况：如果字符串长度为奇数，我们立即返回 false，因为它无法形成有效的括号字符串。

时间复杂度：

• 两次传递（从左到右和从右到左）都需要线性时间 O(n)，其中 n 是字符串的长度。因此，总体时间复杂度为 O(n)，这对于输入大小限制是有效的。

这个解决方案在给定的约束下正确处理了问题。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是检查括号字符串是否有效的详细内容。更多信息请关注PHP中文网其他相关文章！