LeetCode 32:Longest Valid Parentheses

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 "()()"

和之前那个Valid Parentheses不同,这里要找出左右括号能匹配完的最长子串,不太好做,参考了下保存indexde方法,首先看一个具体例子

NewImage

这里返回的最长子串为index 2~11,返回值为10

通过一个stack来保存string的index,如果是(,入栈;如果是),又有很多情况:

(1)假如此时stack里为空,也就是没有(来和新来的)匹配,那么新来的)没啥用,也不会构成满足要求的子串,但是要记录下一个有效位置的起点,从下一位开始:lastValidIndex = i + 1

(2)假如此时stack里非空,这里又有两种情况:

A:stack里不止一个(,那么每次来一个),就将栈顶的index出栈,直到新来的)全部匹配完,上图例子就是这种情况,用xmind记录一下逻辑

NewImage

B:stack里就只剩一个(,那么新来一个),将栈顶的index出栈,这样(被匹配光了,那么这一轮就结束了,maxLength = i – lastValidIndex + 1,比如(),lastValidInde = 0,i = 1,maxLength=2

但是A和B是独立的,因此每次计算maxLength需要和上一次返回的maxLength进行对比

大致源码如下

package com.lihuia.leetcode;

import java.util.Stack;

/**
* Copyright (C), lihuia.com
* FileName: Solution
* Author: lihui
* Date: 2018/12/15
*/

public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int lastValidIndex = 0;
int maxLength = 0;

for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
if (stack.empty()) {
lastValidIndex = i + 1;
} else {
stack.pop();
if (! stack.empty()) {
maxLength = i - stack.peek() > maxLength ? i - stack.peek() : maxLength;
} else {
maxLength = i - lastValidIndex + 1 > maxLength ? i - lastValidIndex + 1 : maxLength;
}
}
}
}
return maxLength;
}
}

还有人用动态规划的方法,有兴趣可以学习下

发表回复