20. Valid Parentheses

问题

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

思路

这道题很简单，就是一个经典的栈的例子——表达式中的括号符号匹配。

  • 遇见了左括号就进栈
  • 遇见了右括号就出栈
    • 如果栈为空，出错
    • 如果出栈元素不是匹配的括号，出错

这里解决出括号匹配用了一个小tick，就是利用ASCII码，匹配的括号的ascii码都不会相差太远

  • ‘(‘ ‘)’ 相差1
  • ‘[‘ ‘]’ ‘{‘ ‘}’ 相差2
  1. public class Solution {
  2.     public boolean isValid(String s) {
  3.         if(s.length() == 0)
  4.             return false;
  5.         Stack<Character> stack = new Stack<Character>(); // 创建堆栈对象 
  6.         for(int i = 0;i < s.length(); i++)
  7.         {
  8.             if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
  9.                 stack.push(s.charAt(i));
  10.             if(s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}')
  11.             {
  12.                 if(stack.empty()) return false;
  13.                 char out = stack.pop();
  14.                 if(out - s.charAt(i) > 2)
  15.                     return false;
  16.             }
  17.         }
  18.         if(stack.empty())
  19.             return true;
  20.         return false;
  21.     }
  22. }