题目链接
leetcode在线oj题——使括号有效的最少添加
题目描述
只有满足下面几点之一,括号字符串才是有效的:
- 它是一个空字符串,或者
- 它可以被写成 AB (A 与 B 连接), 其中 A 和 B 都是有效字符串,或者
- 它可以被写作 (A),其中 A 是有效字符串。
给定一个括号字符串 s ,在每一次操作中,你都可以在字符串的任何位置插入一个括号
- 例如,如果 s = “()))” ,你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
题目示例
输入:s = “())”
输出:1
输入:s = “(((”
输出:3
题目提示
- 1 <= s.length <= 1000
- s 只包含 ‘(’ 和 ‘)’ 字符。
解题思路
这道题的意思是,想要把字符串变成类似(…(())…)这种形式需要添加多少个括号
我们一般使用具有先进后出特性的栈来解决括号匹配的问题,而对于这道题,由于只有一种类型的括号,因此只需要计数即可
先分析一下以下几种情况:
如果第一个字符就是右括号,那么肯定没有左括号与之匹配,因此至少需要添加一个左括号
如果第一个字符是左括号,那么后面遇到任何一个右括号都可以与之匹配
我们初始化leftCount = 0,answer = 0,从头到尾遍历字符串的每一个字符
如果遇到左括号:
leftCount就++
如果遇到右括号:
如果leftCount<=0,说明答案需要添加一个左括号与之匹配,因此answer++
如果leftCount>0,那么就将前面的一个左括号与之匹配,因此leftCount–
代码
class Solution {
public int minAddToMakeValid(String s) {
int leftCount = 0;
int answer = 0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '('){
leftCount++;
} else {
if(leftCount > 0){
leftCount--;
} else {
answer++;
}
}
}
answer += leftCount;
return answer;
}
}