20. Valid Parentheses

Problem:

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:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

思路：

Solution (C++):

bool isValid(string s) {
    if (s.empty())      return true;
    stack<char> stk{};
    int len = s.length();
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            stk.push(s[i]);
        else if (s[i] == ')') {
            if (stk.empty() || stk.top() != '(')  return false;
            else  stk.pop();
        }
        else if (s[i] == '}') {
            if (stk.empty() || stk.top() != '{')  return false;
            else  stk.pop();
        }
        else if (s[i] == ']') {
            if (stk.empty() || stk.top() != '[')  return false;
            else  stk.pop();
        }
    }
    if (!stk.empty()) return false;
    return true;
}

性能：

Runtime: 0 ms  Memory Usage: 6.2 MB

思路：

Solution (C++):

性能：

Runtime: ms  Memory Usage: MB