杭州网站维护外包,怎么攻击php做的网站,软件开发培训班机构,婚纱网站建设目的1. 题目
给定一个由 ( 和 ) 括号组成的字符串 S#xff0c;我们需要添加最少的括号#xff08; ( 或是 )#xff0c;可以在任何位置#xff09;#xff0c;以使得到的括号字符串有效。
从形式上讲#xff0c;只有满足下面几点之一#xff0c;括号字符串才是有效的( 和 ) 括号组成的字符串 S我们需要添加最少的括号 ( 或是 )可以在任何位置以使得到的括号字符串有效。
从形式上讲只有满足下面几点之一括号字符串才是有效的
它是一个空字符串或者它可以被写成 AB A 与 B 连接, 其中 A 和 B 都是有效字符串或者它可以被写作 (A)其中 A 是有效字符串。
给定一个括号字符串返回为使结果字符串有效而必须添加的最少括号数。
示例 1
输入())
输出1示例 2
输入(((
输出3示例 3
输入()
输出0示例 4
输入()))((
输出4提示
S.length 1000
S 只包含 ( 和 ) 字符。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 5470. 平衡括号字符串的最少插入次数 medium
用栈来匹配未匹配的在栈内留下来
class Solution {
public:int minAddToMakeValid(string S) {stackchar stk;for(int i 0; i S.size(); i){if(stk.empty())stk.push(S[i]);else{if(stk.top()( S[i]))stk.pop();elsestk.push(S[i]);}}return stk.size();//未匹配的字符数}
};or 用左右括号计数来表示
class Solution {
public:int minAddToMakeValid(string S) {int left 0;int right 0;for(char c:S){if(c() left;else{if(left0) //右括号可以与之匹配left--;else //右括号没有相应的左括号匹配right;} }return leftright;}
};
