# 20. Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.

## Ex

Example 1:

Input: s = "()"
Output: true


Example 2:

Input: s = "()[]{}"
Output: true


Example 3:

Input: s = "(]"
Output: false


## Constraints:

1 <= s.length <= 10^4

s consists of parentheses only ‘()[]{}’.

# 解题思路

() 这种是否成对出现，最常见的思路就是使用 stack。

# 代码实现

## V1-stack 版本

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
* @author d
* @since 1.0.0
*/
public class T020_ValidParentheses {

private static final Map<Character, Character> MAP = new HashMap<>(4);

static {
MAP.put(')', '(');
MAP.put('}', '{');
MAP.put(']', '[');
}

/**
* 简单思路
*
* 【效果】
*
* Runtime: 1 ms, faster than 98.79% of Java online submissions for Valid Parentheses.
* Memory Usage: 37.4 MB, less than 70.07% of Java online submissions for Valid Parentheses.
*
* @param s 字符串
* @return 结果
* @since v1
*/
public boolean isValid(String s) {
if(null == s || s.length() == 0) {
return true;
}
// 奇数
if(s.length() % 2 != 0) {
return false;
}

Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if(c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
// 开始 pop
if(stack.isEmpty()) {
return false;
}

char pop = stack.pop();
char expectPop = MAP.get(c);

if(pop != expectPop) {
return false;
}
}

}

return stack.isEmpty();
}

}


## v2-基于数组模拟 stack

/**
* 优化思路：
*
* 使用数组+指针替代 Stack
*
* <p> project: leetcode-ValidParentheses </p>
* <p> create on 2020/6/16 22:49 </p>
*
* @author binbin.hou
* @since 2020-6-16 22:49:35
*/
public class T020_ValidParenthesesV2 {

/**
* 大道至简
*
* 【效果】
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Parentheses.
* Memory Usage: 37.1 MB, less than 95.67% of Java online submissions for Valid Parentheses.
*
* @param s 字符串
* @return 结果
* @since v1
*/
public boolean isValid(String s) {
int length = s.length();
char[] stack = new char[length];

for(int i = 0; i < length; i++) {
char c = s.charAt(i);

switch (c) {
case '{':
case '[':
case '(':
break;
case '}':
return false;
}
break;
case ']':
return false;
}
break;
case ')':
return false;
}
break;
}
}

}

}


# 32. Longest Valid Parentheses

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

## Ex

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".


Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


Example 3:

Input: s = ""
Output: 0


## Constraints:

0 <= s.length <= 3 * 10^4

s[i] is ‘(‘, or ‘)’.

（1）暴力算法

（2）双指针

# V1-基本实现

    /**
* 最简单的思路：
*
* 1. 通过双指针，两边移动。截取 substring
* 2. 通过 020 的方法，判断字符串是否为 valid，是返回 j-i
* 3. i j 重合，返回 0
*
* 这种解法：会在 222 CASE 超时
*
* @param s 字符串
* @return 结果
*/
public int longestValidParentheses(String s) {
//0.1 都不是
if(s.length() <= 1) {
return 0;
}

// 这个复杂度是 o(N^3)，肯定没戏
for (int stepLen = s.length(); stepLen >= 2; stepLen--) {
// 逆序，本质是双指针
for(int i = 0; i < s.length()-1; i++) {
// fast-return
if(i + stepLen > s.length()) {
break;
}

String subString = s.substring(i, i+stepLen);

if(isValid(subString)) {
return stepLen;
}
}
}

// 没有
return 0;
}

/**
* 大道至简
*
* T020
*
* @param s 字符串
* @return 结果
* @since v1
*/
public static boolean isValid(String s) {
// 奇数个，不可能满足
if(s.length() % 2 != 0) {
return false;
}

Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if(c == '(') {
stack.push(c);
} else {
// 开始 pop
if(stack.isEmpty()) {
return false;
}

char pop = stack.pop();
char expectPop = '(';

if(pop != expectPop) {
return false;
}
}

}

return stack.isEmpty();
}


isValid 判断是否合法，是 T20 的一个简化版本。

two-java-solutions-with-explanation-stack-dp-short-easy-to-understand

# V2-基于 stack

## 基于堆栈的思路

// Stack solution 10ms
The idea is simple, we only update the result (max) when we find a "pair".
If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
EX: "( )( )"
stack: -1, 0,
when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
In this example it's -1. So the gap is "current_index" - (-1) = 2.

The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.


例子： "()()"



### 个人理解

)(()) 为例子思考

2   // (
1   // (
0   // )
-1  // 初始


1   // (
0   // )
-1  // 初始


i = 4 的时候，也会匹配。

0   // )
-1  // 初始


## java 实现

    /**
* 基于 stack 的差异对比
*
* @param s 字符串
* @return 结果
*/
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int result = 0;
stack.push(-1);

for(int i = 0; i < s.length(); i++) {
// 当前为 )，且 stack 中上一个刚好为 (
if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
stack.pop();
result = Math.max(result, i - stack.peek());
} else {
stack.push(i);
}
}

return result;
}


# V2-基于 DP

## 他山之石

//DP solution 4ms
The idea is go through the string and use DP to store the longest valid parentheses at that point.
take example "()(())"
i : [0,1,2,3,4,5]
s : [( ,) ,( ,( ,) ,) ]
DP:[0,2,0,0,2,6]

1, We count all the ‘(‘.
2, If we find a ‘)’ and ‘(‘ counter is not 0, we have at least a valid result size of 2. “()"
3, Check the the one before (i - 1). If DP[i - 1] is not 0 means we have something like this “(())” . This will have DP “0024"
4, We might have something before "(())”. Take "()(())” example, Check the i = 1 because this might be a consecutive valid string.


i：[0,1,2,3,4,5]
s : [( ,) ,( ,( ,) ,) ]
DP：[0,2,0,0,2,6]


1，我们计算所有的’(‘。

2，如果我们发现一个’)’和’(‘计数器不为0，我们至少有一个有效的结果大小为2。“()”

3、检查前一项(i - 1)。 如果 DP[i - 1] 不是 0 意味着我们有这样的东西 “(())” 。 这将有 DP “0024”

4，我们可能在“（（））”之前有一些东西。以“（）（（））”为例，检查i = 1，因为这可能是一个连续的有效字符串。

## java 实现

public class Solution {
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()];
int result = 0;
int leftCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftCount++;
} else if (leftCount > 0){
// 当前位置满足最长，() 的长度为2。在上一个最长的基础上+2
dp[i] = dp[i - 1] + 2;

dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0;

// 计算最大的结果
result = Math.max(result, dp[i]);
leftCount--;
}
}
return result;
}
}


dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0; 这句话时最令人困惑的？

# 参考资料

https://leetcode.com/problems/valid-parentheses/

https://leetcode.com/problems/longest-valid-parentheses/description/

https://leetcode.com/problems/longest-valid-parentheses/solutions/14278/two-java-solutions-with-explanation-stack-dp-short-easy-to-understand/