Within 10 lines in Python to solve it.


  • 5
    K
      def longestValidParentheses(self, s):
        """ as the ")" will not effect the final result, which acts as a dummy  element to
            make the all the  original elements of s equivalently, 
            otherwise the first element needs to be dealt with separately. 
        """ 
        s = ")" + s  
        stack, ans = [], 0
        for index in xrange(len(s)):
          element = s[index]
          if element == ")" and stack and stack[-1][1] == "(":
            stack.pop()
            ans = max(ans, index - stack[-1][0])
          else:
            stack.append((index, element))
        return ans

  • 0
    N

    It's brilliant ! But could you give more explanation about your algorithm? What is the purpose of appending "(" and ")" to the original string? I'm a little bit confused.


  • 3
    H

    shortened 2 lines:

        def longestValidParentheses(self, s):
            stack, ans = [], 0
            for i,v in enumerate(")"+s):
              if v == ")" and stack and stack[-1][1] == "(":
                stack.pop()
                ans = max(ans, i - stack[-1][0])
              else:
                stack.append((i, v))
            return ans

  • 0
    G

    I think he meant if you add ")" in the beginning of s it doesn't change the longest valid substring. But it does allow you to use the loop directly without handling the starting case.


Log in to reply
 

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