题目描述（简单难度）

20. Valid Parentheses - 图1

括号匹配问题。

如果只有一种括号，我们完全可以用一个计数器 count ，遍历整个字符串，遇到左括号加 1 ，遇到右括号减 1，遍历结束后，如果 count 等于 0 ，则表示全部匹配。但如果有多种括号，像 ( [ ) ] 这种情况它依旧会得到 0，所以我们需要用其他的方法。

栈！

遍历整个字符串，遇到左括号就入栈，然后遇到和栈顶对应的右括号就出栈，遍历结束后，如果栈为空，就表示全部匹配。

  1. public boolean isValid(String s) {
  2.     Stack<Character>  brackets  = new Stack<Character>(); 
  3.     for(int i = 0;i < s.length();i++){
  4.         char c = s.charAt(i);
  5.         switch(c){
  6.             case '(':
  7.             case '[':
  8.             case '{':
  9.                 brackets.push(c); 
  10.                 break;
  11.             case ')':
  12.                 if(!brackets.empty()){
  13.                     if(brackets.peek()== '('){
  14.                         brackets.pop();
  15.                     }else{
  16.                         return false;
  17.                     }
  18.                 }else{
  19.                     return false;
  20.                 }
  21.                 break;
  22.             case ']':
  23.                 if(!brackets.empty()){
  24.                     if(brackets.peek()=='['){
  25.                         brackets.pop();
  26.                     }else{
  27.                         return false;
  28.                     }
  29.                 }else{
  30.                     return false;
  31.                 }
  32.                 break;
  33.             case '}':
  34.                 if(!brackets.empty()){
  35.                     if(brackets.peek()=='{'){
  36.                         brackets.pop();
  37.                     }else{
  38.                         return false;
  39.                     }
  40.                 }else{
  41.                     return false;
  42.                 }
  44.         }
  45.     }
  47.     return brackets.empty();
  48. }

时间复杂度：O（n）。

空间复杂度：O（n）。

总

如果学过数据结构，一定写过计算器，括号匹配问题一定遇到过的。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情