C++ using stack with explain


  • 0
    X

    hope this is easier to understand, bcz i confuse about some without using stack. If you know better way, pleassse reply and I will learn. Thanks!

    class Solution {
    public:
        bool isValid(string s) {
            int len = s.length();
            if (len < 1) return true;
    
    /*====================================================================================
        V 1.0 : use heap, get a left put into, get a right and check if it matches.
        Time: O(n), space: O(1)
    *///==================================================================================
            stack<char> getChar; 
            
            for(int i = 0; i < len; i++){
                if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                    getChar.push(s[i]); 
                } else { // getting ),},]
                    if(getChar.empty()){ return false; }
                    else {
                        char opening = getChar.top();
                        getChar.pop(); 
                        if(opening == '(' && s[i] == ')') continue; 
                        if(opening == '[' && s[i] == ']') continue; 
                        if(opening == '{' && s[i] == '}') continue; 
                        // else
                        return false; 
                    }
                }
            }
            return getChar.empty(); // BUG: do NOT return true here, remember check stack.empty()!!!
            
        }
    };
    

Log in to reply
 

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