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。
遇到 ( 开始字符，我们就 push 入栈；遇到 ) 字符，就把 stack 中的字符 pop 出栈。
最后字符串遍历结束，然后 stack 刚好也是空的，说明 string 是符合条件的。
代码实现
V1-stack 版本
我们引入一个 map，记录下几个成对字符的映射关系。
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，实现类似的效果。
/**
* 优化思路：
*
* 使用数组+指针替代 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];
int headIx = 0;
for(int i = 0; i < length; i++) {
char c = s.charAt(i);
switch (c) {
case '{':
case '[':
case '(':
stack[headIx++] = c;
break;
case '}':
if(headIx == 0 || stack[--headIx] != '{') {
return false;
}
break;
case ']':
if(headIx == 0 || stack[--headIx] != '[') {
return false;
}
break;
case ')':
if(headIx == 0 || stack[--headIx] != '(') {
return false;
}
break;
}
}
return headIx == 0;
}
}
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 ‘)’.
初步思路
看到这个，我们结合 T20，如何判断字符串是否为有效的成对括弧并不难。
那么，如何找到最长的呢？
（1）暴力算法
我们把所有可能的 substring 构建出来，然后判断是否合法，找到最长的一个。
（2）双指针
一个字符串，想找到最长的合法 substring。
比较自然的其实会想到双指针的方式，i 从左边开始，j 从右边开始。
二者逐渐向中间靠拢，判断 substring 是否合法，合法返回，则此时就是最长的。
实现起来，个人采用的是固定步长的方式。
V1-基本实现
为了实现双指针，我们采用固定步长的方式。
从 i=0 开始，逐步向右，步长逐渐变短。
/**
* 最简单的思路：
*
* 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.
这个想法很简单，我们只在找到“pair”时更新结果 (max)。
如果我们找到一对。
我们把这对扔掉，看看当前和以前的无效之间的差距有多大。
例子： "()()"
堆栈：-1、0、
当我们到达索引 1“)”时，窥视是“(”，所以我们弹出它并查看“(”之前的内容。
在这个例子中它是-1。 所以差距是“current_index” - (-1) = 2。
当我们找到一个“pair”并将 -1 推入堆栈时，这个想法只会更新结果（最大值），首先覆盖所有边缘情况。
个人理解
以 )(()) 为例子思考
一开始的 stack 入栈情况，
2 // (
1 // (
0 // )
-1 // 初始
一直到 i=3 的时候，才会看到 ) 且匹配的情况。
我们把 stack 顶层弹出。然后 i=3 和 stack 当前的顶元素1对比，此时最长的就是 3-1 = 2。
1 // (
0 // )
-1 // 初始
i = 4 的时候，也会匹配。
继续 stack 弹出，i=3 和剩余的 stack 顶层元素对比，此时最长为 4 - 0 = 4。
0 // )
-1 // 初始
这种弹出之后，自然 () 就是一对。然后和剩余的对比，计算最大差异。如果连续都是满足的，则差值刚好也是满足的。
确实比较巧妙。
java 实现
其实这个算法，可以认为是在 isValid 的基础之上的拓展。
/**
* 基于 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;
}
耗时 60ms，超过 55%。
那么，还有其他的解法吗？
V2-基于 DP
自己的初步思路
说实在的，一开始我也想到利用 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.
这个想法是遍历字符串并使用 DP 来存储此时最长的有效括号。
以 “()(())” 为例
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; 这句话时最令人困惑的？
希望这是有道理的——它是 dp 数组中值的索引，就在当前正在计算的括号序列之前
例子解释
如果你有 ()()，当你检查字符串中的最后一个字符时，你的 dp 值将是 [0][2][0][]，并且首先因为你有一个 )，你会 添加 2，但您想添加索引 1 中的值（i - dp[i]，或 3 - 2，给您索引 1），因为它代表您要添加到总计数的相邻有效序列的计数
索引 1 包含 2，因此您将 2 添加到当前 2 并得到正确答案 4
其实就是把前面可能存在的连续满足长度的字符加进来。
这个算法超过 100%，但是个人感觉比较难以想到。
参考资料
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/
