[LeetCode] 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.

解法一: stack

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         unordered_set<char> left = {'(', '[', '{' };
 5         unordered_set<char> right = {')', ']', '}' };
 6         unordered_map<char, char> ht = {{'(',')'}, {'[', ']'}, {'{','}'} };
 7         stack<char> stk;
 8         bool ret = false;
 9         
10         for (int i = 0; i < s.size(); i++){
11             if (left.count(s[i])){
12                 stk.push(s[i]);
13             }else if(right.count(s[i])){
14                 // check empty !!
15                 if (!stk.empty() && ht[stk.top()] == s[i]){
16                     stk.pop();
17                 }else{
18                     return false;
19                 }
20             }else{
21                 return false;
22             }
23         }
24         
25         return stk.empty();
26     }
27 };

博主在Linked-in面试中碰到过这題的简化版: 一个字符串只包含小括号 '(' 或者')', 检查括号匹配是否正确.

该简化版的解法, 可以直接用一个计数器, 而不需要堆栈:

bool matched(String s){
    int left = 0;
        
    for (int i = 0; i < s.size(); i++){
        if (s[i] == '('){
            left++;
            continue;
        }else if (s[i] == ')'){
            if (left > 0){
                left--;
            }else{
                return false;
            } 
        }
    }
    
    return left == 0;
 }