本文涉及知识点

C++栈

LeetCode1249. 移除无效的括号

给你一个由 ‘(’、‘)’ 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
示例 1：
输入：s = “lee(t©o)de)”
输出：“lee(t©o)de”
解释：“lee(t(co)de)” , “lee(t©ode)” 也是一个可行答案。
示例 2：
输入：s = “a)b©d”
输出：“ab©d”
示例 3：
输入：s = “))((”
输出：“”
解释：空字符串也是有效的
提示：
1 <= s.length <= 10⁵
s[i] 可能是 ‘(’、‘)’ 或英文小写字母

栈思想

如果s[i]是( 权值1，）权值-1，其它0。
p[i]等于s[0…i]的权值和。
合法括号的等效条件：任意p[i]>=0， s的权值和为0。
如果p[0…i-1] >= 0，p[i] < 0 则s[i]是)。要想p[i] >=0 ，则s[0…i]中删除一个括号，任意一个)。
在s[0…i]中删除任意一个)，对p[x] (x>i)的影响是一样的。故删除s[i]。
如果t = p.back() > 0，则删除最后一个(， 直到p.back()为0。则最后一个（的下标是i1。
则p[i1…] >= t，删除s[i1] 这些字符的权值和 >= t-1 即 >= 0
一，从小到大计算p[i]，如果p[i] < 0 ,则s[i]= * p[i]=0。可以用cur代替p[i]。
二，从大到i 将s 的后cur个（改成 *
三，删除*。

代码

核心代码

class Solution {
		public:
			string minRemoveToMakeValid(string s) {
				int cur = 0;
				for (auto& ch : s) {
					if ('(' == ch) {
						cur++;
					}
					else if (')' == ch) {
						if (0 == cur) {
							ch = '*';
						}
						else {
							cur--;
						}
					}
				}
				for (int i = s.length() - 1; cur; i--) {
					if ('(' == s[i]) {
						s[i] = '*';
						cur--;
					}
				}
				auto it = remove(s.begin(), s.end(), '*');
				s.erase(it, s.end());
				return s;
			}
		};

单元测试

string s;
		TEST_METHOD(TestMethod11)
		{
			s = "lee(t(c)o)de)";
			auto res = Solution().minRemoveToMakeValid(s);
			AssertEx(string("lee(t(c)o)de"), res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "a)b(c)d";
			auto res = Solution().minRemoveToMakeValid(s);
			AssertEx(string("ab(c)d"), res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "))((";
			auto res = Solution().minRemoveToMakeValid(s);
			AssertEx(string(""), res);
		}