20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

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.

Thoughts

字符串由三种括号组成，问括号是否能匹配。stack的经典应用: 括号匹配。

Code

/*
 * @lc app=leetcode id=20 lang=cpp
 *
 * [20] Valid Parentheses
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
       stack<char> sta;
       for (const auto c : s) {
            switch(c) {
                case '{':
                    sta.push('}');
                    break;
                case '[':
                    sta.push(']');
                    break;
                case '(':
                    sta.push(')');
                    break;
                default:
                    if (sta.empty() || sta.top() != c) return false;
                    sta.pop();
            }
       }
       return sta.empty();
    }
};
// @lc code=end

Analysis

做题耗时: 10 min

Errors:

1. 当最后stack不为空也是非法的。

时空复杂度都是O(n).