Valid Parentheses Problem
Description
LeetCode Problem 20.
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.
Example 1:
1
2
Input: s = "()"
Output: true
Example 2:
1
2
Input: s = "()[]{}"
Output: true
Example 3:
1
2
Input: s = "(]"
Output: false
Example 4:
1
2
Input: s = "([)]"
Output: false
Example 5:
1
2
Input: s = "{[]}"
Output: true
Constraints:
- 1 <= s.length <= 10^4
- s consists of parentheses only ‘()[]{}’.
Sample C++ Code
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
class Solution {
public:
bool isValid(string s) {
stack<char> paren;
for (char c: s) {
if ((c == '(') || (c == '[') || (c == '{')) {
paren.push(c);
} else {
if (paren.empty())
return false;
if ((c == ')') && paren.top() != '(')
return false;
if ((c == ']') && paren.top() != '[')
return false;
if ((c == '}') && paren.top() != '{')
return false;
paren.pop();
}
}
if (paren.empty())
return true;
else
return false;
}
};