。使括号有效的最小添加量

921。使括号有效的最少添加

难度：中等

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

括号字符串有效当且仅当：

• 它是空字符串，
• 可以写为AB（A与B连接），其中A和B是有效字符串，或者
• 可以写成(A)，其中A是一个有效的字符串。

给你一个括号字符串 s。一步操作即可在字符串的任意位置插入括号。

• 例如，如果 s = "()))"，则可以插入左括号“(()))”或右括号“())))”。

返回使 s 有效所需的最小移动次数.

示例1：

• 输入： s = "())"
• 输出： 1

示例2：

• 输入： s = "((("
• 输出： 3

约束：

• 1
• s[i] 是 '(' 或 ')'。

解决方案：

我们需要确定需要添加多少个左括号或右括号才能使输入字符串有效。有效的字符串意味着每个左括号 '(' 都有相应的右括号 ')'。

我们可以使用简单的计数器方法来解决这个问题：

• 我们使用变量balance来跟踪左括号和右括号之间的当前平衡。
• 我们使用另一个变量加法来计算所需的最小括号数。

方法：

1. 循环遍历字符串 s 的每个字符。
2. 如果字符是“(”，则余额加 1。
3. 如果字符是')'，则余额减1：
   • 如果余额变为负数，则意味着右括号比左括号多。我们需要添加一个左括号来平衡它，因此将加法加 1 并将余额重置为 0。
4. 循环结束时，如果balance大于0，说明有不匹配的左括号，所以添加balance。

让我们用 PHP 实现这个解决方案：921。使括号有效的最少添加

<?php /**
 * @param String $s
 * @return Integer
 */
function minAddToMakeValid($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s1 = "())";
echo minAddToMakeValid($s1);  // Output: 1

$s2 = "(((";
echo minAddToMakeValid($s2);  // Output: 3
?>

解释：

• 对于字符串 s = "())"：
  • 当遇到第二个 ')' 时，余额变为负数，因此添加量会增加。
  • 最后余额为0，加法为1，所以我们需要加1才能使字符串有效。
• 对于字符串 s = "(((":
  • 余额变为 3，因为末尾有 3 个不匹配的“(”。
  • 结果是加法余额，即 0 3 = 3。

此解决方案的时间复杂度为 O(n)，其中 n 是字符串的长度，还有一个空格O(1) 的复杂度，因为我们只使用了几个变量。

联系链接

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

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

• 领英
• GitHub

以上是。使括号有效的最小添加量的详细内容。更多信息请关注PHP中文网其他相关文章！