【动态规划】C++算法：最长有效括号

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

LeetCoe:32 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”

输出：2

解释：最长有效括号子串是 “()”

示例 2：

输入：s = “)()())”

输出：4

解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”

输出：0

参数范围：

0 <= s.length <= 3 * 10⁴

s[i] 为 ‘(’ 或 ‘)’

分析

有效括号有两个等效规则，本文用到了其中一个规则：

• ()是有效括号
• 如果A是有效括号，则(A)也是有效括号。简称：包括。如：()() 变成(()())
• 如果A和B都是有效括号，则AB 也是有效括号。简称拼接。如：(()) 和()拼接成(())()

从小到大枚举有效括号的结尾。如果s[i]不是‘）’,忽略。对于每个结尾，分两步：

• 一，计算最长包括。
• 二 ，计算最长拼接。

最长包括

如果dp[i-1]是’（‘,则最长包括是dp[i-1]为2。

如果’）‘ 且dp[i-1]匹配的’(‘的前一个字符为’( ，则dp[i] = 2 + dp[i-1]。dp[i-1]必须不为0。

最长拼接

dp[i]匹配的’(‘的前一个字符为pre，则dp[i] += dp[pre]。dp[i]必须不为0。

注意：不能第一轮枚举所有的包括，第二轮枚举所有的拼接。比如：(()())

代码

核心代码

class Solution {
public:
	int longestValidParentheses(string s) {
		if (s.empty())
		{
			return 0;
		}
		m_c = s.length();		
		vector dp(m_c);		
		for (int i = 0; i < m_c; i++)
		{
			if ('(' == s[i])
			{
				continue;
			}
			if (i - 1 < 0)
			{
				continue;
			}
			//理括号的包括
			if ('(' == s[i - 1])
			{
				dp[i] = 2 ;				
			}
			else
			{
				const int pre = i -1 -  dp[i - 1];
				if (dp[i-1] && (pre>=0)&&('('==s[pre]))
				{
					dp[i] = dp[i - 1]+2;
				}
			}
			//处理拼接
			if (dp[i] <= 0)
			{
				continue;
			}
			const int pre = i - dp[i];
			if (pre >= 0)
			{
				dp[i] += dp[pre];
			}
		}	

		return *std::max_element(dp.begin(), dp.end());
	}
	int m_c;
};

测试用例

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

template
void Assert(const vector& v1, const vector& 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.longestValidParentheses(s);
		Assert(2, res);
	}
	{
		Solution sln;
		s = "";
		auto res = sln.longestValidParentheses(s);
		Assert(0, res);
	}
	{
		Solution sln;
		s = ")()())";
		auto res = sln.longestValidParentheses(s);
		Assert(4, res);
	}
	{
		Solution sln;
		s = "(()())";
		auto res = sln.longestValidParentheses(s);
		Assert(6, res);
	}

	

}

2022年12月版

class Solution {

public:

int longestValidParentheses(string s) {

if (“” == s)

{

return 0;

}

const int c = s.length();

//dp[i]表示以s[i]结尾的合法串长度，非法0

vector dp©;

for (int i = 1; i < c; i++)

{

const char& ch = s[i];

if (‘(’ == ch)

{

continue;

}

if (‘(’ == s[i – 1])

{

dp[i] = ( i >= 2 ? dp[i – 2] :0 ) + 2;

}

else

{

if (dp[i – 1] > 0)

{

int iBegin = (i – 1) – dp[i – 1] + 1;

iBegin–;

if ((iBegin >= 0) && s[iBegin] == ‘(’)

{

dp[i] = dp[i – 1] + 2;

if (iBegin > 0)

{

dp[i] += dp[iBegin – 1];

}

}

			 }

		 }
	 }
	 return *std::max_element(dp.begin(),dp.end());
 }

};

2023年8月版

class Solution {

public:

int longestValidParentheses(string s) {

m_c = s.length();

if (0 == m_c)

{

return 0;

}

vector vRet(m_c);

stack sta;

for (int i = 0 ; i < m_c ; i++ )

{

const auto& ch = s[i];

if (‘(’ == ch)

{

sta.emplace(i);

}

else

{

if (sta.size())

{

int left = sta.top();//与之匹配的左括号

sta.pop();

vRet[i] = (i – left + 1);

if (left > 0)

{

vRet[i] += vRet[left – 1];

}

}

}

}

return *std::max_element(vRet.begin(), vRet.end());

}

int m_c;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。