【LeetCode Easy】020 Valid Parentheses

栏目: 编程工具 · 发布时间: 5年前

内容简介：“()” "[]" "{}"三种括号匹配问题，判断参数字符串是否满足匹配要求如：“({[]})” true “[{})” falseNote:空串为true

Easy 020 Valid Parentheses

Description:

“()” "[]" "{}"三种括号匹配问题，判断参数字符串是否满足匹配要求

如：“({[]})” true “[{})” false

Note:空串为true

My Solution:

括号匹配问题是栈的典型应用，遇到左括号，入栈，遇到右括号，看栈顶是否是相应的左括号，若不是，则false
时间复杂度O(n)
代码如下：

public boolean isValid(String s) {
     if(s.length()==0){
         return true;
     }
     Stack<Character> stack = new Stack<>();
     for(char c:s.toCharArray()){
         if(c == '(' || c == '{' || c == '['){
             stack.push(c);
         }else if(stack.size()==0){
             return false;
         }
         else if(c == ')' && stack.peek() == '('){
             stack.pop();
         }else if(c == ']' && stack.peek() == '['){
             stack.pop();
         }else if(c == '}' && stack.peek() == '{'){
             stack.pop();
         }else
             return false;
     }
     if(stack.size() == 0){
         return true;
     }
     return false;
 }