LeetCode 20. Valid Parentheses 原创Java参考解答

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 == ']'); 
    }     
}

相关题目

LeetCode All in One 原创题目讲解汇总

发表评论

您的电子邮箱地址不会被公开。