leetcode-20 Valid Parentheses

20. Valid Parentheses

Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

Analyse

思路是用栈，如果栈顶是(，下一个字符是)，就把栈顶的(出栈，[、{也是一样，最后看栈是否为空就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isValid(string s)
{
    stack<char> stk;
    for (char c : s)
    {
        if (stk.empty() || c == '(' || c == '[' || c == '{')
        {
            stk.push(c);
            continue;
        }

        char top = stk.top();
        if ((top == '(' && c == ')') ||
            (top == '[' && c == ']') ||
            (top == '{' && c == '}'))
        {
            stk.pop();
        }
        else
        {
            return false;
        }
    }

    return stk.empty();
}

看了下LeetCode上其他的代码，我觉得我的这个版本挺好的，就不介绍其他代码了，思路都是一样的