Leetcode Study Day 26

Valid Parentheses

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
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

My solution

My solution is to use a stack to store the characters: If the input char is a left parenthes, I push it into the stack. If it is not, we check whether the top of the stack is the corresponding left parenthes. If it is, we pop the top of the stack. If it is not, we return false. Also, I checked whether the stack is empty when the next char is a right parenthes, if it is, we return false because it is invalid. After the iteration, we check whether the stack is empty. If it is, we return true. If it is not, we return false.

class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) return true;
        int n = s.size();
        vector<char> stack;
        stack.push_back(s[0]);
        for (int i = 1; i < n; i++){
            if (s[i] == '(' ||s[i] == '{'||s[i] == '[' ){
                stack.push_back(s[i]);
            }
            else if (stack.empty() && s[i]  == ')' || stack.empty() && s[i] == '}' ||stack.empty() && s[i] == ']')
                return false;
            else if (s[i] == ')' && stack[stack.size()-1] == '(' || s[i] == '}' && stack[stack.size()-1] == '{'||s[i] == ']'  && stack[stack.size()-1] == '[' ){
                stack.pop_back();
            }
            else
                return false;
        }
        if (stack.size() == 0)
            return true;
        return false;
    }
};

Improved Solution

I found that I actually use a vector as a stack, so I can use a stack instead.
The main idea of this improved solution is once we have a left paranthes, we can push the responding right paranthes into the stack. Then if we face a right paranthes, we can just compare it to the top of the stack, if it is not equal, return false, if it is equal, we can pop the top. At the end of the iteration, we check whether the stack is empty. If it is, we return true. If it is not, we return false.

class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) return true;
        int n = s.size();
        stack<char> stack;
        for (int i = 0; i < n; i++){
            if(s[i] == '{')
                stack.push('}');
            else if(s[i] == '(')
                stack.push(')');            
            else if(s[i] == '[')
                stack.push(']');
            else if (stack.empty() || stack.top() != s[i])
                return false;
            else stack.pop();
        }
        return stack.empty();
    }
};