题目介绍
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 | Input: "()" |
2 | Output: true |
Example 2:
1 | Input: "()[]{}" |
2 | Output: true |
Example 3:
1 | Input: "(]" |
2 | Output: false |
Example 4:
1 | Input: "([)]" |
2 | Output: false |
Example 5:
1 | Input: "{[]}" |
2 | Output: true |
判断一个字符串是不是合法的，字符串只由括号组成。空字符串也认为合法
解
1 | class Solution { |
2 | public: |
3 | bool isValid(string s) { |
4 | if (s.size() == 0) { |
5 | return true; |
6 | } |
7 | if (s.size() % 2 == 1) { |
8 | return false; |
9 | } |
10 | stack<char> stk; |
11 | for (size_t i = 0; i < s.size(); i++) { |
12 | char c = s[i]; |
13 | if (c == '{' || c == '[' || c == '(') { |
14 | stk.push(c); |
15 | } else { |
16 | if (stk.size() == 0) { |
17 | return false; |
18 | } else if (c == '}') { |
19 | char c2 = stk.top(); |
20 | if (c2 != '{') { |
21 | return false; |
22 | } else { |
23 | stk.pop(); |
24 | } |
25 | } else if (c == ']') { |
26 | char c2 = stk.top(); |
27 | if (c2 != '[') { |
28 | return false; |
29 | } else { |
30 | stk.pop(); |
31 | } |
32 | } else if (c == ')') { |
33 | char c2 = stk.top(); |
34 | if (c2 != '(') { |
35 | return false; |
36 | } else { |
37 | stk.pop(); |
38 | } |
39 | } |
40 | } |
41 | } |
42 | return stk.size() == 0; |
43 | } |
44 | }; |
Runtime: 4 ms
Memory Usage: 8.3 MB
