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

Barbara Streisand
发布: 2024-10-10 06:09:02
原创
826 人浏览过

. Minimum Add to Make Parentheses Valid

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中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!