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 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
class Solution {
public:
bool isValid(string s) {
stack<char> stack;
int idx = 0;
if(s.size() == 0){
return true;
}
while(idx < s.size()){
if( s[idx] == '(' || s[idx] == '[' || s[idx] == '{' ){
stack.push(s[idx]);
}
else if ( (s[idx] == ')' && !stack.empty() && stack.top() == '(') ||
(s[idx] == '}' && !stack.empty() && stack.top() == '{') ||
(s[idx] == ']' && !stack.empty() && stack.top() == '[')
){
stack.pop();
}
else {
return false;
}
idx++;
}
if(stack.empty()) {
return true;
}
return false;
}
};
