Coding Spirit

一位程序员,比较帅的那种

0%

Algorithm Puzzles: Valid Parentheses

Algorithm Puzzles everyday every week sometimes: Valid Parentheses

Puzzle

Puzzle from leetcode:

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

Solution

It’s an easy puzzle can be easily resolved via stack:

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
class Solution {
public:
bool isValid(const std::string& s) {
std::stack<char> stack;
for (auto it = s.begin(); it != s.end(); ++it) {
switch (*it) {
case '(':
case '[':
case '{':
stack.emplace(*it);
break;
case ')':
if (!stack.empty() && stack.top() == '(') {
stack.pop();
} else {
return false;
}
break;
case ']':
if (!stack.empty() && stack.top() == '[') {
stack.pop();
} else {
return false;
}
break;
case '}':
if (!stack.empty() && stack.top() == '{') {
stack.pop();
} else {
return false;
}
break;
default:
return false;
}
}
if (stack.empty()) {
return true;
}
return false;
}
};

To simplify case-branches, maybe we can use a hash map to find target stack.top().