### leetcode Question 120: Valid Parentheses

Valid Parentheses

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Analysis:
Idea is not complex.
Use a stack to store the chars, scan from the 1st to the last char in string s.
( [ { are free to push in the stack.
When meets ) if stack top is (, then pop (.
When meets ] if stack top is [, then pop [.
When meets } if stack top is {, then pop {.
Otherwise return false

In the end, if the stack is empty, return true. (to handle "()(" case )

Code:

class Solution {
public:
bool isValid(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
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()){return false;}
if ((s[i]==')') && (st.top()!='(')) {return false;}
if ((s[i]=='{') && (st.top()!='}')) {return false;}
if ((s[i]=='[') && (st.top()!=']')) {return false;}
st.pop();
}

}
return st.empty();
}
};


#### 1 comment:

1. There is an error

In line 12,13 .. } instead of { and ] instead of [

if ((s[i]=='}') && (st.top()!='{')) {return false;}
if ((s[i]==']') && (st.top()!='[')) {return false;}