Question: http://oj.leetcode.com/problems/longest-valid-parentheses/
Question Name: Longest Valid Parentheses
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | class Solution: # @param s, a string # @return an integer def longestValidParentheses(self, s): stack = [] # The leftmost ")"s are useless to form a valid parentheses for item in s.lstrip(")"): if item == "(": stack.append(item) else: if stack[-1] == "(": # A valid parentheses is found stack.pop() stack.append(2) elif len(stack) > 1 and stack[-2] == "(": # A valid parentheses is found # # stack[-1] != "(", otherwise the previous if block # will be executed. # stack[-1] != ")", otherwise, in the previous round, # a valid parentheses is found, and ")" should not # be in the stack # So stack[-1] must be a number. # temp =stack.pop() stack.pop() stack.append(temp + 2) else: # We should start a new search for the remaining part. # And any content in the remaining part can NOT form # a valid parentheses with previous content. stack.append(")") continue # Compress the previous valid parentheses # For example, with "()()",after dealing with the last ")" # the stack would be [2,2], we try to compress into one unit # as [4]. # After compression, we could guarantee, if current procession # letter is ")", and there is a previous matching "(", there # will be only one or zero integer between them in the stack. while len(stack) > 1 and isinstance(stack[-2], int): temp = stack.pop() temp += stack.pop() stack.append(temp) # Remove the non-number elements stack = [item for item in stack if isinstance(item,int)] if len(stack) == 0: return 0 else: return max(stack) |