# 20. Valid Parentheses
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:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
# Solution
Approach 1: Stacks.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '(' || s[i] == '{' || s[i] == '[')
st.push(s[i]);
else if (st.empty() || // Need to check if the stack is empty.
(s[i] == ')' && st.top() != '(') ||
(s[i] == '}' && st.top() != '{') ||
(s[i] == ']' && st.top() != '['))
return false;
else
st.pop();
}
return st.empty(); // Need to check if the stack is empty.
}
};
class Solution {
public:
bool isValid(string s) {
stack<char> st;
charMap *umap = new charMap();
for (int i = 0; i < s.size(); ++i)
{
if (umap->umap.find(s[i]) != umap->umap.end())
st.push(s[i]);
else if (st.empty() || // Need to check if the stack is empty.
umap->umap[st.top()] != s[i]) // Use st.top() as the index.
return false;
else
st.pop();
}
return st.empty(); // Need to check if the stack is empty.
}
private:
struct charMap
{
unordered_map<char,char> umap;
charMap()
{
umap['('] = ')';
umap['{'] = '}';
umap['['] = ']';
}
};
};