Fork me on GitHub

Leetcode-NINE-LongestValidParentheses

发表于 | 分类于 | 阅读次数:

Longest Valid Parentheses

Description

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

Example

  1. Example 1:

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

  2. Example 2:

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

Analysis

题目意思为，给定一个只包含左括号 ‘(‘ 和右括号 ‘)’的字符串，找出其中最长的合法括号字串，即该字串满足左右括号匹配原则。

如果这是一道简单的括号匹配题，那么非常简单，是一道栈的使用练习题：左括号入栈，右括号匹配栈顶元素，成功则出栈，失败则不合法；最栈非空也为不合法。

这个合法匹配问题，给出了一部分的解题思路。因为在合法的字符串中，左括号与右括号的匹配是一一对应的，即无法对应其他括号。这也是可以利用栈来操作的基础。那么我们就可以写出一个 $O(2n)$ 的解法了：

  1. 通过栈操作，将所有匹配括号打上 tag
  2. 扫描 tag，得到最长的 tag 串

Accept Picture

Accept

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int longestValidParentheses(string str) {
  int size = str.size(), ans = 0, temp = 0;
  stack<int> s;
  vector<bool> v(size, false);

for(int i = 0; i < size; ++i) {
  if (str[i] == '(')  s.push(i);
  else {
    if (!s.empty()) {
      v[s.top()] = true;
      v[i] = true;
      s.pop();
    }
  }
}

  for (auto i : v) {
    temp = i ? temp + 1 : 0;
    ans = max(temp, ans);
  }

  ans = max(temp, ans);
  return ans;
}

Further Thinking

这道题是否可以利用 DP 来做呢？是可以的。
我们定义 l[m] 为以 str[m] 结尾的最长合法字串的长度。
那么对于任意一个 l[i] (0 < i < n)，我们可以计算它的值：

  • str[i] 是 ‘(‘，那么 l[i] = 0，因为不存在以 ‘(‘ 结尾的合法串
  • str[i] 是 ‘)’，那么需要考察前一个括号
    • 如果 str[i-1] 是 ‘(‘，那么 str[i-1] 和 str[i] 是匹配的，因为括号匹配规则中不存在跨越最近匹配的情况，那么 l[i] = l[i-2] + 2
    • 如果 str[i-1] 是 ‘)’，那么需要考察与 str[i-1] 匹配的最长串前的符号 str[i-1-l[i-1]]，由此确定 str[i] 是否可以加入这个串。
      • 如果 str[i-1-l[i-1]] 是 ‘(‘，那么 str[i] 与 str[i-1-l[i-1]]是匹配的，即 ( str[i-1-l[i-1]+1]...str[i-1] )，其中 str[i-1-l[i-1]...str[i-1]是合法串，整个串也是合法的，那么 l[i] = l[i-1] + 2。但是，还不够详细，因为在这个串前的串可能是合法的，即 previousString ( str[i-1-l[i-1]+1]...str[i-1] ) 中的 previousString 可以是合法的。所以 l[i] = l[i-1] +2 + l[i-2-l[i-1]]
      • 如果 str[i-1-l[i-1]] 是 ‘)’，那么 str[i-1-l[i-1]] 与 str[i] 无法匹配，l[i] = 0

这样，就把 l[i] 的计算公式给全了，也就是我们的 DP 式。其中，l[0] 一定是0，因为单独无法成为合法串，所以计算 n-1 次即可。伪代码如下，算法复杂度为 $O(n)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Index validation is not contained in the pseudocode
l[0...n-1] = 0
ans = 0

for (i in [1, n-1]):
  if (str[i] == ')'):
    if (str[i-1] == '('):
      l[i] = l[i-2] + 2
      ans = max(l[i], ans)
    else:
      if (str[i-1-l[i-1]] == '('):
        l[i] = l[i-1] + 2 + l[i-2-l[i-1]]
        ans = max(l[i], ans)

return ans

AC 截图如下：

AC

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int longestValidParentheses(string str) {
  int size = str.size(), ans = 0;
  vector<int> l(size, 0);

  for (int i = 1; i < size; ++i) {
    if (str[i] == ')') {
      if (str[i-1] == '(') {
        l[i] = i-2 >= 0 ? (l[i-2] + 2) : 2;
        ans = max(ans, l[i]);
      } else {
        if (i - l[i-1] - 1 >= 0 && str[i - l[i-1] - 1] == '(') {
            l[i] = l[i-1] + 2 + (i-l[i-1]-2 >= 0 ? l[i-l[i-1]-2] : 0);
            ans = max(l[i], ans);
        }
      }
    }
  }
  return ans;
}