C++ 0ms 2 simple solutions with stack


  • 0
    Z
    class Solution {
    public:
    bool isValid(string s) {
        //return solution1(s);
        return solution2(s);
    }
    private:
    bool solution1(string s){
        if(s == "") return true;
        if(s[0] == ')' || s[0] == ']' || s[0] == '}') return false;
        if(s.length() % 2 != 0) return false;
        map<char, char> m;
        m[')'] = '(';
        m[']'] = '[';
        m['}'] = '{';
        stack<char> st;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
                st.push(s[i]);
            else{
                if(m[s[i]] != st.top()) return false;
                st.pop();
            }
        }
        return st.empty() ? true : false;
    }
    bool solution2(string s){
        if(s == "") return true;
        if(s[0] == ')' || s[0] == ']' || s[0] == '}') return false;
        if(s.length() % 2 != 0) return false;
        stack<char> st;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
                st.push(s[i]);
            else{
                if(s[i] != st.top()+1 && s[i] != st.top()+2) return false;
                st.pop();
            }
        }
        return st.empty() ? true : false;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.