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. class Solution {
  4. public:
  5.     bool isValid (string const& s) {
  6.         string left = "([{";
  7.         string right = ")]}";
  8.         stack<char> stk;
  10.         for (auto c : s) {
  11.             if (left.find(c) != string::npos) {
  12.                 stk.push (c);
  13.             } else {
  14.                 if (stk.empty () || stk.top () != left[right.find (c)])
  15.                     return false;
  16.                 else
  17.                     stk.pop ();
  18.             }
  19.         }
  20.         return stk.empty();
  21.     }
  22. };

相关题目

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