Leetcode 32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

We can use stack, or iterate from head and tail.

Solution 1:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {integer}
    def longestValidParentheses(self, s):
        L = len(s)
        if L <= 1:
            return 0
        stk, maxlen, last = [], 0, -1
        for i in xrange(L):
            if s[i] == '(':
                stk.append(i)
            else:
                if stk == []:
                    last = i
                else:
                    stk.pop()
                    if stk == []:
                        maxlen = max(maxlen, i - last)
                    else:
                        maxlen = max(maxlen, i - stk[len(stk) - 1])
        return maxlen

Run Time: 100 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        longest = 0
        
        start, depth = -1, 0
        for i in xrange(len(s)):
            if s[i] == "(":
                depth += 1
            else:
                depth -= 1
                if depth < 0:
                    start, depth = i, 0
                elif depth == 0:
                    longest = max(longest, i - start)
        
        start, depth = len(s), 0
        for i in reversed(xrange(len(s))):
            if s[i] == ")":
                depth += 1
            else:
                depth -= 1
                if depth < 0:
                    start, depth = i, 0
                elif depth == 0:
                    longest = max(longest, start - i)
        
        return longest

Run Time: 76 ms