【字符串】【括号匹配】【广度优先】301. 删除无效的括号

作者推荐

【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

本文涉及知识点

字符串 括号匹配 广度优先

LeetCode301 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]
示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]
示例 3：
输入：s = “)(”
输出：[“”]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

预备知识

合法括号的定义：
一，()是合法括号。
二,A和B是合法括号。则AB也是合法括号。A=() B = () 则()()是合法括号。
三，(A)是合法括号。A=()()，则(()())是合法括号。
性质：
num=0,从左到右解析括号，遇到(++，遇到)–。性质一：num任何时候都不能为负。性质二：num最终必须为0。
定义是性质的充分条件容易证明，下面来证明必要条件。
令num1[i]是s[0,i]的num之和。
n u m 1 [ i ] 是合法括号 → i 一定不为 0 因为 n u m 1 [ 0 ] 只能是 1 或 − 1 n u m 1 [ i − 1 ] > = 0 , 所以 s [ i ] 只能是 ) ，否则 n u m 1 [ i ] > = 0 + 1 s [ 0 ] 一定是 ( ，否则 n u m 1 [ 0 ] 为 − 1 { 将其拆分 s [ 0 , j ] 和 s ( j , i ] 仍然符合性质 存在 j ≠ i 且 n u m 1 [ j ] = = 0 删除最左的 ( ，最右的 ) ，变成 n u m s [ 1 , i ) o t h e r num1[i]是合法括号 \rightarrow i一定不为0 因为num1[0]只能是1或-1\\ num1[i-1] >=0 ,所以s[i]只能是)，否则num1[i] >= 0+1 \\ s[0]一定是(，否则num1[0] 为-1 \\

{将其拆分s[0,j]和s(j,i]仍然符合性质存在j≠i且num1[j]==0删除最左的(，最右的)，变成nums[1,i)other
num1[i]是合法括号→i一定不为0因为num1[0]只能是1或−1num1[i−1]>=0,所以s[i]只能是)，否则num1[i]>=0+1s[0]一定是(，否则num1[0]为−1{将其拆分s[0,j]和s(j,i]仍然符合性质删除最左的(，最右的)，变成nums[1,i)​存在j=i且num1[j]==0other​
num1[j]不为0且大于等于0 → \rightarrow → num1[j]大于等于1
移除（后，nums1[j]全部-- 任然符合性质一
s[i]合法 → \rightarrow → num1[i]==0 → \rightarrow → num1[i-1]为1
移除(后，变成0，符合性质二。
不断拆分，知道s的长度为2为止。

广度优先

初始字符为空。
hasAdd 记录增加了多少字符。
num 记录字符的权值和，(为1，)为-1。
{ p r e 各字符串，尝试删除 ) n u m < 0 增加字符 h a s A d d < s . l e n g t h 结束 n u m = 0 删除 ( o t h e r

{pre各字符串，尝试删除)num<0增加字符hasAdd<s.length结束num=0删除(other
⎩ ⎨ ⎧​pre各字符串，尝试删除)增加字符结束删除(​num<0hasAdd<s.lengthnum=0other​
删除）时，无需判断，因为只会让其它)的num变大或不变。
删除)时，需要判断，因为可能让某个)的num变成负数。

代码

核心代码

class Solution {
public:
	vector<string> removeInvalidParentheses(string s) {
		int num = 0;
		unordered_set<string> pre = { "" };
		int iDelLeft=0,iDelRight = 0;
		for (int i = 0; ; i++)
		{
			unordered_set<string> dp;
			const int hasAdd = i - iDelLeft -iDelRight;
			if (num < 0)
			{//删除一个右括号
				iDelRight++;
				num++;
				for (const string& str : pre)
				{
					for (int j = 0; j < str.length(); j++)
					{
						if (')' == str[j])
						{
							dp.emplace(str.substr(0, j) + str.substr(j + 1));
						}
					}
				}
			}
			else if (hasAdd < s.length())
			{
				if ('(' == s[hasAdd])
				{
					num++;
				}
				else if (')' == s[hasAdd])
				{
					num--;
				}
				for (const string& str : pre)
				{
					dp.emplace(str + s[hasAdd]);
				}
			}
			else 
			{
				if (num > 0)
				{//删除一个左括号
					num--;
					iDelLeft++;
					for (const string& str : pre)
					{
						for (int j = 0; j < str.length(); j++)
						{
							if ('(' == str[j])
							{
								dp.emplace(str.substr(0, j) + str.substr(j + 1));
							}
						}
					}
				}
				else
				{
					break;
				}
			}
			dp.swap(pre);
		}
		vector<string> vRet;
		for (const string& str : pre)
		{
			if (IsVilid(str))
			{
				vRet.emplace_back(str);
			}
		}
		return vRet;
	}
	bool IsVilid(const string& str)
	{
		int num = 0;
		for (const auto& ch : str)
		{
			if ('(' == ch)
			{
				num++;
			}
			else if (')' == ch)
			{
				num--;
			}
			if (num < 0)
			{
				return false;
			}
		}
		return 0 == num;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	string s;
	{
		Solution sln;
		s = ")()(";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "()" }, res);
	}
	{
		Solution sln;
		s = ")(";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "" }, res);
	}
	{
		Solution sln;
		s = "()())()";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "(())()", "()()()" }, res);
	}
	
	{
		Solution sln;
		s = "(a)())()";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "(a())()","(a)()()" }, res);
	}

	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

简洁版

class CBracket
{
public:
	static int ToInt(const char& ch)
	{
		if ('(' == ch)
		{
			return 1;
		}
		return (')' == ch) ? -1 : 0;
	}
	static bool IsVilid(const string& str)
	{
		int num = 0;
		for (const auto& ch : str)
		{
			num += ToInt(ch);
			if (num < 0)
			{
				return false;
			}
		}
		return 0 == num;
	}
};
class Solution {
public:	
	vector<string> removeInvalidParentheses(string s) {
		int num = 0;
		unordered_set<string> pre = { "" };
		int iHasAdd = 0;
		while(true)
		{
			unordered_set<string> dp;	
			auto Del = [&pre,&dp](char ch)
			{
				for (const string& str : pre)
				{
					for (int j = 0; j < str.length(); j++)
					{
						if (ch == str[j])
						{
							dp.emplace(str.substr(0, j) + str.substr(j + 1));
						}
					}
				}
			};
			if (num < 0)
			{//删除一个右括号
				num++;
				Del(')');
			}
			else if (iHasAdd < s.length())
			{
				num += CBracket::ToInt(s[iHasAdd]);
				for (const string& str : pre)
				{
					dp.emplace(str + s[iHasAdd]);
				}
				iHasAdd++;
			}
			else 
			{
				if (num > 0)
				{//删除一个左括号
					num--;	
					Del('(');
				}
				else
				{
					break;
				}
			}
			dp.swap(pre);
		}
		vector<string> vRet;
		for (const string& str : pre)
		{
			if (CBracket::IsVilid(str))
			{
				vRet.emplace_back(str);
			}
		}
		return vRet;
	}
	
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87

2023年4月版

class Solution {
public:
vector removeInvalidParentheses(string s) {
int iNeedDelLeft = 0, iNeedDelRight = 0;
{
for (int i = 0; i < s.length(); i++)
{
const char& ch = s[i];
if ((‘(’ == ch) || (‘)’ == ch))
{
vRangeIndexs.emplace_back(i);
}
if (‘(’ == ch)
{
iNeedDelLeft++;
}
if (‘)’ == ch)
{
if (iNeedDelLeft > 0)
{
iNeedDelLeft–;
}
else
{
iNeedDelRight++;
}
}
}
}
m_iMaskNum = 1 << vRangeIndexs.size();
auto Is = [&](const int iMask)
{
int iNum = 0;
for (int j = 0; j < vRangeIndexs.size(); j++)
{
if (iMask & (1 << j))
{//此位置删除
continue;
}
const char& ch = s[vRangeIndexs[j]];
if (‘(’ == ch)
{
iNum++;
}
if (‘)’ == ch)
{
iNum–;
}
if (iNum < 0)
{
return false;
}
}
return 0 == iNum;
};
std::unordered_set setRet;
for (int iMask = 0; iMask < m_iMaskNum; iMask++)
{
if (bitcount(iMask) != (iNeedDelLeft + iNeedDelRight))
{
continue;
}
if (!Is(iMask))
{
continue;
}
std::vector indexs,subIndexs;
for (int i = 0; i < s.length(); i++)
{
indexs.emplace_back(i);
}
for (int j = 0; j < vRangeIndexs.size(); j++)
{
if (iMask & (1 << j))
{//此位置删除
subIndexs.emplace_back(vRangeIndexs[j]);
}
}
vector v;
string str;
std::set_difference(indexs.begin(), indexs.end(), subIndexs.begin(), subIndexs.end(), std::back_inserter(v));
for (const auto& tmp : v)
{
str += s[tmp];
}
setRet.emplace(str);
}
return vector(setRet.begin(), setRet.end());
}
int m_iMaskNum;
vector vRangeIndexs;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136176018"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！