⚔ LeetCode | 32. Longest Valid Parentheses

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 32. Longest Valid Parentheses

Difficulty : Hard

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

Example 1:

1
2
3
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Analysis

这道hard题看上去就像一道普通的括号匹配，但是仔细一看其实不然，他要求找出最长的连续的可以匹配的括号对的长度。这就需要在括号匹配的算法上做一下小改变了。

Approach 1

普通的括号匹配主要是用到了栈，而这里的基本算法核心也是需要用到栈，只不过需要在处理入栈和出栈的时候做多一点处理。

普通的括号匹配需要用到一个栈，然后遍历字符串

  • 如果当前字符是(：
    • 上一个字符是(：入栈
    • 上一个字符是）：括号不匹配
  • 如果当前字符是)
    • 上一个字符是(，就可以视为是一个完整的匹配：栈顶出栈
    • 上一个字符是)：括号不匹配

由于题目需要找出最长的连续匹配的括号，因此，即使是不匹配，依旧需要保留在栈中，并且记录他们的位置，以便后面计算连续匹配的长度。

因此算法的基本思想为：

声明两个栈stack和pos，前者记录字符，后者记录位置

遍历字符串：

  • 如果当前字符是)，并且上一个字符为(：
    • stack和pos的栈顶出栈
  • 其他情况：
    • 将当前字符入栈stack，当前位置入栈pos

遍历一遍过后，pos里面就剩下得到不匹配的括号的位置，因此他们相邻之间的差就是匹配的连续括号对的长度。

再此之前，我们还需要将头和尾的位置放入pos的头和尾。

我们来看个例子，比如字符串()())()，处理过后得到的不匹配的括号的位置为[4]

加上头和尾，不匹配的括号位置就变为[-1, 4, 7]

那么匹配的连续括号对长度就分别为4 - (-1) - 1 = 4和7 - 4 - 1 = 2，正好代表着()()和()

其中他们最大值就是问题所求的值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestValidParentheses(s string) int {
	var stack []int32
	var pos []int
	for i, c := range s {
		if len(stack) != 0 && c == ')' && stack[len(stack) - 1] == '(' {
			stack = stack[:len(stack) - 1]
			pos = pos[:len(pos) - 1]
		} else {
			stack = append(stack, c)
			pos = append(pos, i)
		}
	}
	pos = append([]int{-1}, pos[:]...)
	pos = append(pos, len(s))
	max := 0
	for i := 1; i < len(pos); i ++ {
		lengths := pos[i] - pos[i  - 1] - 1
		if lengths > max {
			max = lengths
		}
	}
	return max
}

这个算法只需要遍历一次字符串，因此时间复杂度为O(n)，空间复杂度为O(n)

Approach 2

上面介绍了用堆栈的解法，所需要的空间复杂度为O(n)，这里说一下一种不需要额外空间的解法。

这种解法的主要思想就是通过由左到右以及由右到左的扫描，然后记录左右括号的计数，当左右括号数量相等的时候，就说明存在括号匹配，并且把左右括号计数清零。

这种做法需要两次扫描，一次从左到右，再一次从右到左，不管一组连续的括号对左右分别是什么，都保证被扫描出来。

代码如下：

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
func longestValidParentheses(s string) int {
	left, right, max := 0, 0, 0
	for i := range s {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			if 2 * right > max {
				max = 2 * right
			}
		} else if right >= left {
			left, right = 0, 0
		}
	}
	left, right = 0, 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			if 2 * left > max {
				max = 2 * left
			}
		} else if  left >= right {
			left, right = 0, 0
		}
	}
	return max
}

这个算法的时间复杂度为O(n)，空间复杂度为O(1)，比上一种算法所要需要的空间要少得多。

Summary

这道hard题，看上去也不是很难，如果你写过一些基本括号匹配相关的算法，再扩展一下，这道题很容易就会被解出来。除了堆栈、扫描，还有一种通过数组动态规划的算法，这里就不详细介绍了，其基本思想也是差不多的，时间复杂度和空间复杂度和堆栈的做法是一样的。

土豪通道
0%