> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/stack/jie-he-qian-mian-de-shu-ru/valid-parentheses.md).

# 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

```cpp
/*
 * @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).