My 0ms C++ answer using stack and map


  • 3
    H

    #include <stack>
    #include <map>
    class Solution {
    public:
    bool isValid(string s) {

        std::stack<char> temp;
        std::map<char,char> myMap={{')','('},{']','['},{'}','{'}};
    
        for(int i=0;i<s.size();i++){
            if(s[i]=='('||s[i]=='['||s[i]=='{')temp.push(s[i]);
            else{
                if(temp.empty()||temp.top()!=myMap[s[i]])return false;
                temp.pop();
            }
        }
        return temp.empty()?true:false;
    }
    

    };


  • 0
    G

    Few comments:

    1. Iterate over s using "for each" loop: for (auto& c : s). You'll save multiple accesses to s.
    2. Once you do #1, just use 'c' to check if it's in myMap and use the iterator returned to get the matching opening bracket for validation.
    3. If you completed 1+2 above, you can flip the "if" and skip the hard coded comparison (which is efficient but ugly).
    4. Lastly, temp.empty() return a bool, so there's no point using the ?: operator like you did. Just return it.

    Bottom line, I like your idea, especially since this more or less what I did :)
    here:

    class Solution {
    public:
        bool isValid(string s) {
            stack<char> st;
            // not use unordered_map - I didn't check performance, but my assumption 
            // is that a balanced, non-changing tree, will be more efficient for such a 
            // small set of keys, than going through a hash function every time.
            map<char,char> m = {{')','('},{'}','{'},{']','['}};
            for (auto& c:s) {
                // check if 'c' is a key in the map, which means it's a closing bracket
                auto it = m.find(c);
                if (it != m.end()) {
                    // it's a closing bracket
                    if (st.empty() || it->second != st.top()) return false;
                    st.pop();
                }
                else {
                    // it's an opening bracket - we don't check if it's valid, since anyway it will fail validation eventually
                    // we sacrifice a little CPU time for code cleanliness
                    st.push(c);
                }
            }
            
            return st.empty();
        }
    };
    

  • 0
    H

    Thank you for your comment. Yours is a little better, indeed.


Log in to reply
 

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