Leetcode20.有效的括号

@Time 20191123

1.题目描述

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

2.解法

使用栈

首先在拿到这道题的时候,方向已经指明,就是使用栈来解决问题,大概的思路也有,就是使用新进来的char和栈顶元素进行比较,但是在如何存储,也就是如何表示两个括号之间是一队的问题上,思考就戛然而止了,最终题解给出的答案是使用HashMap存储对应的括号对,看来今后的算法题中,HashMap该用还得用

class Solution{
  private HashMap<Character,Character> map ;
  public Solution(){
    //take the code easier to read
    //initialize the map
    map = new HashMap<Character,Character>();
    map.put(')','(');
    map.put(']','[');
    map.put('}','{');
  }
  public boolean isValid(String s ){
    //use a stack to solve this problem
    Stack<Character> stack = new Stack<Character>();
    if(s.length()%2 == 1){
      return false;
    }
    //use a loop to detect
    for(int i = 0;i < s.length();i++){
      char c = s.charAt(i);
      //get the top element of stack ,if it is null,return '#'
        if(this.map.containsKey(c)){
        char topElement = stack.isEmpty()? '#': stack.pop();
        if(this.map.get(c) != topElement)
          return false;
            }
        else{
        stack.push(c);
        if(stack.size() > s.length()/2){
          return false;
        }
      }
    }
    return stack.isEmpty();
  }
}

首先在构造函数Solution()中创建HashMap对象,并完成相应的初始化,注意存储的顺序是map.put(')','(');,后面的括号')'为key,这样可以和栈顶的'('作比较,首先一个增加算法健壮性的操作就是

if(s.length()%2 == 1){ return false; }

如果括号的数量为奇数,那么一定不能进行完全匹配,直接返回false,接着对s字符串的每一个字符做压栈操作,如果为括号的左半部分,那么this.map.containsKey(c)一直为false,直接入栈,如果压栈的符号为括号的右半部分,那么将当前栈顶的字符弹出啦,并作比较,如果相等,继续下一个字符入栈,如果不相等,直接返回false。