One stack in C with O(n)


  • 0
    W

    ‘’‘
    typedef struct {
    char ch;
    int indx;
    }Node;

    typedef struct {
    Node* base;
    Node* top;
    int size;
    }SqStack;

    class Solution {
    public:
    int longestValidParentheses(string s) {
    SqStack st;
    int len = s.size();
    st.base = (Node*)malloc((sizeof(Node))* (len + 1));
    st.size = len;
    st.base->indx = 0;
    st.base->ch = 0;
    st.top = st.base;

    	int num = 0, tmp = 0, count = 0;
    	for (int i = 0; i < len; i++) {
    		if (st.top->ch == '(' && s[i]==')') {
    			count = st.top->indx;
    			--st.top;
    			st.top->indx += count + 1;
    			int preIndx = st.top->indx;
    			num = preIndx > num ? preIndx : num;
    		} else {
    			++st.top;
    			st.top->ch = s[i];
    			st.top->indx = 0;
    		}
    	}
    	
    	return num << 1;
    }
    

    };
    ’‘’


Log in to reply
 

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