LeetCode 20 Valid Parentheses

思路

遍历整个string，遇到前半部分就入栈，遇到后半部分就判断栈顶是否与之匹配，不匹配则直接返回false，匹配则继续遍历。【注意，遇到后半部分时，如果栈为空，则不用匹配，直接返回false】
最后判断栈是否为空，若为空，则说明匹配成功；否则，匹配失败。

代码

class Solution {
    public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++) {
    if(s.charAt(i) == ')') {
    if(stack.isEmpty() || stack.pop() != '(') {
    return false;}} else if(s.charAt(i) == ']') {
    if(stack.isEmpty() || stack.pop() != '[') {
    return false;}} else if(s.charAt(i) == '}') {
    if(stack.isEmpty() || stack.pop() != '{') {
    return false;}} else {
    stack.push(s.charAt(i));}}return stack.isEmpty();}
}

复杂度

时间复杂度O(n), 空间复杂度O(n).