数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中最小删除以使括号有效
假设我们有一个包含 '('、')' 和小写英文字母的字符串 s。我们必须删除最少数量的括号（ '(' 或 ')'，位于任何位置），以便生成的括号字符串有效，并返回任何有效的字符串。当满足所有这些条件时，括号字符串才有效：
它是空字符串，仅包含小写字符，或者
它可以写成 AB 的形式（A 与 B 连接），其中 A 和 B 是有效的字符串，或者
它可以写成 (A) 的形式，其中 A 是有效的字符串。
因此，如果输入类似于“a)b(c)d”，则输出将是“ab(c)d”。
为了解决这个问题，我们将遵循以下步骤：
定义一个栈 st
对于 i 从 0 到 s 的大小
如果 s[i] = ‘(’，则将 i 插入 st
否则，当 s[i] 为 ‘)’ 时，
如果栈不为空，则从栈中弹出，否则 s[i] = ‘*’
当 st 不为空时，
s[栈顶元素] = ‘*’
从栈中弹出
ans := 空字符串
对于 i 从 0 到 s 的大小 - 1
如果 s[i] 不为 ‘*’，则 ans := ans + s[i]
返回 ans
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack <int> st;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(')st.push(i);
else if(s[i] == ')'){
if(!st.empty())st.pop();
else s[i] = '*';
}
}
while(!st.empty()){
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++){
if(s[i] != '*')ans += s[i];
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}输入
"a)b(c)d"
输出
ab(c)d
更新于：2020年5月2日
383 次查看
广告