题解 | #括号序列#

本题有两个思路：
思路一：“替换思想”，只要是有效的括号对，那()或[]或{}必定会成对出现,那我们就可以用“”(啥也没有的字符串)代替有效的括号对，检查是否被替换就可以括号对是否有效。注意：这里的括号可能出现嵌套，所以需要循环去重复替换。
代码如下：

public boolean isValid (String s) {
       boolean flag=true;
      //flag用来标记前面一次的括号序列是否被替换过，若没有被替换，说明已经结束了
      while(flag){
        String str =s;
        s=s.replace("()","").replace("[]","").replace("{}","");
        if(str.equals(s)){//本次替换后和上次一样，说明本次没替换。
          flag=false;//替换工作结束，标记改为false
        }
      }
      if("".equals(s)){//最后判断括号是否全部被替换
        return true;
      }
      return false;
}

思路二：利用栈的后进先出特点。遍历括号序列，遇到左括号就入栈，遇到右括号就从栈顶拿出一个左括号进行匹配，若括号类型相同，则继续遍历下一个括号；若不相同，就直接返回false.
代码如下：

   public boolean isValid (String s) {
      if(s.length()==1) return false;
      Stack<Character> stack = new Stack();
      for(int i=0;i<s.length();i++){
         if(s.charAt(i)=='(' || s.charAt(i)=='[' ||s.charAt(i)=='{'){
           stack.push(s.charAt(i));
         }else{
           if(stack.size()==0) return false;//看栈是否为空。
           if(match(stack.pop(),s.charAt(i))) continue;//匹配成功就继续遍历
           else return false;//不成功就返回false
         }
      }
      if(stack.size()>0) return false;//最后查看栈是否还有括号
      return true;
    }
  //辅助函数，用于判断两个括号字符似乎否匹配
  public boolean match(char c,char s){
     switch(c){
       case '(':
         if(s==')')return true;
         break;
       case '[':
         if(s==']')return true;
         break;
       case '{':
         if(s=='}')return true;
         break;
     }
    return false;
  }