LeetCode--Valid Parentheses

发表于 | 分类于 |

Given a string 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.

Note that an empty string is also considered valid.

样例：

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

题意：

给出一个字符串，判断其中括号是否匹配，’(‘ –> ‘)’，’[‘ –> ‘]’，’{‘ –> ‘}’

思路：

使用栈来进行判断：

如果是 ‘(‘、’[‘ 、’{‘ 这三个，则入栈

如果遇到 ‘)’、’]’、’}’ 这三个则判断栈顶是否为对应的匹配字符串，如果是则出栈，反之返回 false。

代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    bool isValid(string s) {
        stack<char>st;
        if (!s.empty()) {
            for (int i = 0; i < s.size(); ++i) {                
                if (s[i] == ')') {
                    if (!st.empty()) {
                        char ch = st.top();
                        if (ch != '(')
                            return false;
                        else
                            st.pop();
                    }
                    else return false;
                }
                else if (s[i] == ']') {
                    if (!st.empty()) {
                        char ch = st.top();
                        if (ch != '[')
                            return false;
                        else
                            st.pop();
                    }
                    else return false;
                }
                else if (s[i] == '}') {
                    if (!st.empty()) {
                        char ch = st.top();
                        if (ch != '{')
                            return false;
                        else
                            st.pop();
                    }
                    else return false;
                }
                else
                    st.push(s[i]);
            }
            if(st.empty()) return true;
            else return false;
        }
        else
            return true;
    }
};

Runtime：4ms Memory：8.6MB