My 0ms c++ solution using stack


  • 16
    Y
    bool isValid(string s) {
        stack<char> st;
        for(char c : s){
            if(c == '('|| c == '{' || c == '['){
                st.push(c);
            }else{
                if(st.empty()) return false;
                if(c == ')' && st.top() != '(') return false;
                if(c == '}' && st.top() != '{') return false;
                if(c == ']' && st.top() != '[') return false;
                st.pop();
            }
        }
        return st.empty();

  • 2
    L

    Great! This is my code inspired by your solution. Given ascii

    '(':40    ')':41
    '[':91    ']':93
    '{':123   '}':125
    

    Just use the trick that c/40->1,2,3

    bool isValid(string s) {
        char trick[] = { ')', ']', '}' };
        stack<char> matching;
        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{') {
                matching.push((c / '(') - 1);
            } else if (matching.empty()) {
                return false;
            } else if (c != trick[matching.top()]) {
                return false;
            } else {
                matching.pop();
            }
        }
        return matching.empty();
    }

  • 0
    J

    @leolinabcd I also use the ascii, but I use the different trick.

    bool isValid(string s) {
    	stack<char> it;
    	char temp;
    	for (char c:s) {
    		if(c=='(' || c=='[' || c=='{')
    			it.push(c);	
    		else {
    			if (it.empty()) return false;
    			temp = it.top();
    			if (c - temp != 1 && c - temp != 2)
    				return false;	
    			it.pop();
    		}
    	}
    	return it.empty();
    }

  • 0
    S

    @leolinabcd
    My solution is similar with yours. But what I push into stack is like

    '('+1->')'
    '['+2->']'
    '('+2->')'

    Just judge char is equal or not

    class Solution {
    public:
            bool isValid(string s) {
            int len=s.length(),i;
            stack<char> st;
            for (char& c : s){
                switch (c){
                    case '(':st.push(c+1);break;
                    case '{':
                    case '[':st.push(c+2);break;
                    default:{
                        if ((!st.empty())&&(c==st.top())) st.pop();
                        else return false;
                    }
                }
            }
            return st.empty();
        }
    };

  • 0
    L

    @young_zk said in My 0ms c++ solution using stack:

    bool isValid(string s) {
        stack<char> st;
        for(char c : s){
            if(c == '('|| c == '{' || c == '['){
                st.push(c);
            }else{
                if(st.empty()) return false;
                if(c == ')' && st.top() != '(') return false; ///why  use (if(c==')' and st.top()=='(') return true ) can't accept?
                if(c == '}' && st.top() != '{') return false;
                if(c == ']' && st.top() != '[') return false;
                st.pop();
            }
        }
        return st.empty();

  • 0
    P

    But This is taking 3ms @young_zk


Log in to reply
 

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