LeetCode 20. Valid Parentheses 原创Java参考解答
问题描述
https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
解题思路
这道题是求字符串是否前后括号匹配。输入的字符串只包含'(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’。
只需要一个栈就能帮助解决。从字符串第一个位置开始一一访问每一个字符
- 如果是一种左括号，则放入栈中
- 如果是一种右括号，则检查栈中顶部字符是否是匹配类型的左括号。若栈中顶部字符不匹配或者此时栈中已无前括号，则直接判断该字符串不能前后括号匹配
参考代码
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else {
if (!stack.isEmpty() && isPair(stack.peek(), ch)) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
private boolean isPairParenthesis(char c1, char c2) {
return (c1 == '(' && c2 == ')')
|| (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
}