# Leetcode Valid Parentheses problem solution

In this Leetcode Valid Parentheses problem solution we have given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

## 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;
}
```