**Leetcode 32. Longest Valid Parentheses

本文主要是介绍**Leetcode 32. Longest Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主要两种思路，stack 以及 dp

我想出来的是stack的solution 自己的Dp没A掉，看了别人的Dp思路才懂。

1、最简单易懂的

struct Node {int idx;char c;Node(int idx, char c): idx(idx), c(c) {}
};class Solution {
public:int match(char l, char r) {if ( l == '(' && r == ')' ) {return 2;} else {return 0;}}int longestValidParentheses(string s) {int ans = 0;stack<Node> sta;for (int i = 0; i < s.size(); i++) {if ( sta.size() == 0 || !match( sta.top().c, s[i] ) ) {sta.push(Node(i, s[i]));} else {sta.pop();}}sta.push(Node(s.size(), '|'));int idxs[sta.size()];int len = sta.size();for ( int i = sta.size()-1; i >= 0; i-- ) {idxs[i] = sta.top().idx;sta.pop();}int last_v = 0;for ( int i = 0; i < len; i++ ) {ans = max( idxs[i] - last_v, ans );last_v = idxs[i] + 1;}return ans;}
};

2、干净的stack代码

class Solution {
public:int longestValidParentheses(string s) {stack <int> sta;int ans = 0, l = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {sta.push(i);} else {if (sta.empty()) {l = i + 1;} else {sta.pop();if (sta.empty()) {ans = max( ans, i - l + 1 );} else {ans = max( ans, i - sta.top() );}}}}return ans;}
};

3、dp

class Solution {
public:int longestValidParentheses(string s) {int ans = 0;if (s.size() < 2) return 0;int longest[s.size()];for (int i = 0; i < s.size(); i++) {longest[i] = 0;if (s[i] == ')' && i - 1 >= 0 && i - longest[i - 1 ] - 1 >= 0 && s[ i - longest[i - 1 ] - 1 ] == '(' ) {longest[i] = longest[i-1] + 2 + ( (i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0 );ans = max(ans, longest[i]);}}return ans;}
};

这篇关于**Leetcode 32. Longest Valid Parentheses的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---