- Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
- Example 1:
- Input: "(()"
- Output: 2
- Explanation: The longest valid parentheses substring is "()"
- Example 2:
- Input: ")()())"
- Output: 4
- Explanation: The longest valid parentheses substring is "()()"
题意
找最长的合法左右括号字符串
题解
这道题还蛮难的, 一开始我的 dp 思路错误了 (n3 的复杂度真是不像话)
把 dp 数组设为以当前索引值为末尾的合法字符串的长度就可以做了
- class Solution {
- public:
- int longestValidParentheses(string s) {
- int l = s.length();
- if (l <2)return 0;
- int ans = 0;
- vector<int>dp;
- dp.resize(l);
- for (int i = 0; i <l; i++)
- dp[i] = 0;
- if (s[0] == '('&&s[1] == ')') {
- ans = 2;
- dp[1] = 2;
- }
- for (int i = 2; i < l; i++) {
- if (s[i] == '(')continue;
- if (s[i - 1] == '(')dp[i] = dp[i - 2] + 2;
- else {
- int last = dp[i - 1];
- if (i - last - 1>= 0 && s[i - last - 1] == '(') {
- dp[i] = last + 2;
- if (i - last - 2>= 0)
- dp[i] += dp[i - last - 2];
- }
- }
- ans = max(ans, dp[i]);
- }
- return ans;
- }
- };
- View Code
来源: http://www.bubuko.com/infodetail-2941921.html