Leetcode 20

Questions

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 are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Solution

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        string o_brackets = "([{";
        for(auto k: s){
            if(o_brackets.find(k) != string::npos){
                st.push(k);
            }
            else{
                if(st.empty()) return false;
                if(st.top() == '(' && k == ')') st.pop();
                else if(st.top() == '[' && k == ']') st.pop();
                else if(st.top() == '{' && k == '}') st.pop(); 
                else return false;
            }
        }
        if(st.empty()) return true;
        else return false;
    }
};

Using stack, store all brackets opening, and if there’s matching closing bracket, pop the top of the stack.