C++ solution, using std::map & stack


  • 0
    F
    class Solution {
    public:
        bool isValid(string s) {
            int len = s.size();
            if (len % 2 != 0)
                return false;
        
            map<char, int> tab;
            tab['('] = 1;
            tab[')'] = -1;
            tab['{'] = 2;
            tab['}'] = -2;
            tab['['] = 3;
            tab[']'] = -3;
        
            stack<int> st;
            for (int i = 0; i < len; i++)
            {
                // push numbers into stack until you meets an negative number
                while (tab[s[i]] > 0)
                    st.push(tab[s[i++]]);
                
                // if the first number is negative 
                // or top element of the stack is not the opposite number of tab[s[i]]
                // return false
                if (st.empty() || st.top() + tab[s[i]] != 0) 
                    return false;
                
                st.pop();
            }
            return true;
        }
    };

Log in to reply
 

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