Valid Parentheses

Posted on Edited on In Views:

20.Valid Parentheses

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

1
2
Input: s = "()"
Output: true

Example 2:

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

Example 3:

1
2
Input: s = "(]"
Output: false

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
bool isValid(string s) {
    int s_size = s.size();
    stack<char> stack_char;
    for (char c:s) {
        if (c == '(' || c == '{' || c == '[')stack_char.push(c);
        else if (!stack_char.empty() && c == ')' && stack_char.top() == '(')stack_char.pop();
        else if (!stack_char.empty() && c == ']' && stack_char.top() == '[')stack_char.pop();
        else if (!stack_char.empty() && c == '}' && stack_char.top() == '{')stack_char.pop();
        else return false;
    }
    return stack_char.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> m{{')', '('}, {'}', '{'}, {']', '['}};
        for (char c: s) {
            switch (c) {
                case ')':
                case ']':
                case '}':
                    if (st.empty() || m[c] != st.top()) return false;
                    st.pop();
                    break;
                default:
                    st.push(c);
                    break;
            }
        }
        return st.empty();
    }
};