Valid Parentheses Problem: 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.
- Every close bracket has a corresponding open bracket of the same type.
Example :
Input: s = "()" Output: true
Example :
Input: s = "(]" Output: false
Table of Contents
Problem Solution In Python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
dic = {'(': ')', '[': ']', '{': '}'}
for c in s:
if stack and stack[-1] in "([{" and dic[stack[-1]] == c:
stack.pop()
else:
stack.append(c)
return not stack
Problem Solution In Java
class Solution {
public boolean isValid(String s) {
Stack<Character> stk=new Stack<>();
for(char c:s.toCharArray())
{
if(c=='(' || c=='{' || c=='[')
{
stk.push(c);
}else
{
if(stk.isEmpty()) return false;
if(stk.peek()=='(' &&c!=')') return false;
if(stk.peek()=='[' &&c!=']') return false;
if(stk.peek()=='{' &&c!='}') return false;
stk.pop();
}
}
return stk.isEmpty();
}
}
Problem Solution In C++
class Solution {
public:
char transfer(char c) {
char tc;
switch (c) {
case ')':
tc = '(';
break;
case ']':
tc = '[';
break;
case '}':
tc = '{';
break;
}
return tc;
}
bool isValid(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s.at(i) == '(' || s.at(i) == '[' || s.at(i) == '{')
st.push(s[i]);
if (s.at(i) == ')' || s.at(i) == ']' || s.at(i) == '}') {
if (st.empty()) return false;
if (st.top() == transfer(s[i]))
st.pop();
else
return false;
}
}
if (!st.empty()) return false;
else return true;
}
};
Problem Solution In C
#define CLOSE_PAREN 3
int getType(char c) {
int idx = 0;
switch (c) {
case '(':
idx = 0;
break;
case '{':
idx = 1;
break;
case '[':
idx = 2;
break;
case ')':
idx = 3;
break;
case '}':
idx = 4;
break;
case ']':
idx = 5;
break;
default:
break;
}
return idx;
}
bool isValid(char* s) {
char paren[] = { '(', '{', '[', ')', '}', ']' };
int len = strlen(s);
char *valid = (char*)calloc(len, sizeof(char));
int k = 0;
if(s == NULL || len == 1)
return false;
if (len == 0)
return true;
for (int i=0; i<len; i++) {
int type = getType(s[i]);
if (type < CLOSE_PAREN) {
valid[k++] = s[i];
} else {
if (k>0 && valid[k-1] == paren[type-CLOSE_PAREN]) {
k--;
} else {
return false;
}
}
}
return (k == 0) ? true: false;
}