921. Minimum Add to Make Parentheses Valid
2024-08-23 02:48:08
Given a string S
of '('
and ')'
parentheses, we add the minimum number of parentheses ( '('
or ')'
, and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
- It is the empty string, or
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
is a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Example 1:
Input: "())"
Output: 1
Example 2:
Input: "((("
Output: 3
Example 3:
Input: "()"
Output: 0
Example 4:
Input: "()))(("
Output: 4
Note:
S.length <= 1000
S
only consists of'('
and')'
characters.
Approach #1: C++.[stack]
class Solution {
public:
int minAddToMakeValid(string S) {
int len = S.length();
if (len == 0) return 0;
stack<char> myStack;
myStack.push(S[0]); for (int i = 1; i < len; ++i) {
if (myStack.empty()) myStack.push(S[i]);
else if (myStack.top() == '(' && S[i] == ')') myStack.pop();
else myStack.push(S[i]);
} return myStack.size();
}
};
最新文章
- html5中canvas的使用 获取鼠标点击页面上某点的RGB
- 【PHP&;&;mysqli】
- C++中使用函数指针 【瓦特芯笔记】
- GUI之CCControlExtension
- PowerDesigner创建物理模型
- C#(.Net)知识点记录
- Masonry适配的简单使用
- 使用Spring MVC构建REST风格WEB应用
- 解决Ubuntu SMPlayer播放视频无声音问题
- JS弹出下载对话框以及实现常见文件类型的下载
- python之log
- div变成输入框
- JavaScript几种常见的继承方法
- 将NULL值转化为“”
- 【HNOI2016】树
- HDU 1052(田忌赛马 贪心)
- SPI、I2C、UART三种串行总线协议的区别
- 初探 opencv-python
- IE6,IE7浏览器下 margin 无效的解决方法
- HDU 2161 Primes (素数筛选法)