Title Description

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.

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
      //jdk util包下的stack。泛型内写入的是char的包装类
        Stack<Character> stack = new Stack<>();
      
      //for循环进行遍历
        for(int i = 0; i < s.length();i++){
          //通过charAt 将遍历到的括号存放在 c 中
            char c = s.charAt(i);
          //判断 如果c是 ([{  这三个的一种，那么进行push操作 放到栈的底部
            if(c == '(' || c == '[' ||  c == '{'){
                stack.push(c);
            }else{
              	// 否则 首先判断stack是不是有东西
                if(stack.isEmpty()){
                    return false;
                }
              //定义topChar 存放的为栈顶
                char topChar = stack.pop();
              //此时如果c等于右括号，那么判断栈顶的topChar是否为左括号
                if(c == ')' && topChar != '('){
                    return false;
                }
                if(c == ']' && topChar != '['){
                    return false;
                }
                if(c == '}' && topChar != '{'){
                    return false;
                }
            }
        }
      //最终判断stack是否还有内容
        return stack.isEmpty();
    }
}