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.

分析

无

代码

  1. // Valid Parentheses
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public boolean isValid(String s) {
  5.         final String left = "([{";
  6.         final String right = ")]}";
  7.         Stack<Character> stk = new Stack<>();
  9.         for (int i = 0; i < s.length(); ++i) {
  10.             final char c = s.charAt(i);
  11.             if (left.indexOf(c) != -1) {
  12.                 stk.push (c);
  13.             } else {
  14.                 if (!stk.isEmpty() &&
  15.                         stk.peek() == left.charAt(right.indexOf(c)))
  16.                     stk.pop ();
  17.                 else
  18.                     return false;
  19.             }
  20.         }
  21.         return stk.empty();
  22.     }
  23. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/stack-and-queue/stack/valid-parentheses.html