Search in Rotated Sorted Array II @ LeetCode (Python)
Palindrome Partitioning @ LeetCode (Python)

Longest Valid Parentheses @ LeetCode (Python)

kitt posted @ 2014年4月08日 22:56 in LeetCode , 2906 阅读

用一个栈记录左括号, 右括号和index, 如果当前括号是右括号且栈顶是左括号, 则弹栈并更新maxLen。

Use a stack to record left paren, right paren and index. If current paren is ')' and stack top is '(' then pop up and update maxLen.

 

# 2015-06-08  Runtime: 88 ms
class Solution:
    # @param {string} s
    # @return {integer}
    def longestValidParentheses(self, s):
        # 记录左括号的index,每次出现右括号且可以跟栈顶左括号匹配时,更新一下maxLen
        stack, maxLen = [-1], 0
        for i in xrange(len(s)):
            if s[i] == ')' and stack[-1] != -1 and s[stack[-1]] == '(':
                stack.pop()
                maxLen = max(maxLen, i - stack[-1])
            else:
                stack.append(i)
        return maxLen

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter