LeetCode 032 Longest Valid Parentheses

LeetCode

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.

Example 2:

Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.

Example 3:

Input: s = “”
Output: 0

Constraints:

`0 <= s.length <= 3 10<sup>4</sup>*s[i]is‘(‘, or‘)’`.

题目大意：

最长括号对数。

Stack算法思路(推荐)：

括号题优先考虑用Stack。由于只有单种括号，只需考虑两种不合法情况。
三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空)
难点： 1. 用下标存于stack，方便计算长度。不合法的保留栈中，这样不合法之间的距离-1就是合法的长度

注意事项：

1. Stack存了左右括号，不只存左括号，所以Line 7要验证栈顶为左括号
2. 循环后头尾加-1和s长度，方便头尾计算

Python代码：

def longestValidParentheses(self, s: str) -> int:
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		if s[i] == ')':
			if stack and s[stack[-1]] == '(':  # remember
				stack.pop()
			else:
				stack.append(i)

	# ())(()) # ())
	stack.insert(0, -1)
	stack.append(len(s))
	max_len = 0
	while len(stack) > 1:
		index = stack.pop()
		max_len = max(max_len, index - stack[-1] - 1)
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

DP算法II解题思路：

注意事项：

1. 答案用max_len
2. 条件s[i - 1 - dp[i - 1] - 1]和递归式dp[i - dp[i - 1] - 2]不能越界
3. 递归式要加dp[i - dp[i - 1] - 2]，dp[..]”(“dp..[]”)” 就是第一个递归式，容易忽略

Python代码：

# dp[i] = max -> dp[i-2] + 2 if s[i-2:i] == ()
#             -> dp[i-1] + 2 + dp[i-1-dp[i-1]-2] if s[i-1-dp[i-1]-1]== ( and s[i-1] == )
def longestValidParentheses2(self, s: str) -> int:
	dp = [0] * (len(s) + 1)
	max_len = 0  # remember
	for i in range(2, len(dp)):
		dp[i] = max(dp[i], dp[i - 2] + 2 if s[i - 2:i] == '()' else 0)
		prev_dp = 0  # remember
		if i - dp[i - 1] - 2 >= 0:
			prev_dp = dp[i - dp[i - 1] - 2]
		# remember i - 1 - dp[i - 1] - 1 >= 0
		dp[i] = max(dp[i], dp[i - 1] + 2 + prev_dp if i - 1 - dp[i - 1] - 1 >= 0 and s[i - 1 - dp[i - 1] - 1] == '(' and s[i - 1] == ')' else 0)
		max_len = max(max_len, dp[i])
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

统计算法III解题思路：

括号题另一个常用思路是用统计左右括号数。维护四个变量left, right, res, max_len
当左括号小于右括号数（第一个规律）：重设全部变量
当左括号等于右括号数（第二个规律）：满足两个条件，可以计算res。重设left，right，准备计算下一轮res。不重设res，因为可以连续如()()

注意事项：

1. 上述情况只覆盖了()),不能覆盖((), 因为左括号数在每一位永远都不会等于右括号数。所以旋转180度再做一次。

Python代码：

def longestValidParentheses3(self, s: str) -> int:
	max_len = self.get_max_len(s)
	res = []
	PARENTHESES_DICT = {'(': ')', ')': '('}
	for char in s:
		res.append(PARENTHESES_DICT[char])
	max_len = max(max_len, self.get_max_len(res[::-1]))
	return max_len

def get_max_len(self, s: str) -> int:
	max_len = res = left = right = 0
	for char in s:
		if char == '(':
			left += 1
		if char == ')':
			right += 1
			if left < right:
				left = 0
				right = 0
				res = 0
			if left == right:  # (())), ()()
				res += left * 2
				max_len = max(max_len, res)
				left = 0
				right = 0
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(n)