Leetcode——32.最大有効括弧【###】

@author: ZZQ @software: PyCharm @file: leetcode32_最大有効かっこpy @time: 2018/11/22 19:19
要件:'('および')'のみを含む文字列を指定し、有効なカッコを含む最長のサブ列の長さを見つけます.
例1:

      : "(()"
      : 2
      :           "()"

例2:

      : ")()())"
      : 4
      :           "()()"

考え方:

     1）max_len                。
     2）s_dict             。
     3）start         。
     4）     ，    
     5）     ，a.    s_dict  ，   start  
                 b.   ，s_dict     ，  ，
                        b.1.      ，            【i start     ，  start】i-start+1，  max_len  ；
                        b.2.     ，          ，             【i            】i-s_dict[-1]，  max_Len  。

MACコードは以下の通りである.

class Solution():
    def __init__(self):
        pass

    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        s_len = len(s)
        max_len = 0
        s_dict = []
        i = 0
        start = 0
        while i < s_len:
            if s[i] == '(':
                s_dict.append(i)
            else:
                if len(s_dict) == 0:
                    i += 1
                    start = i
                    continue
                else:
                    s_dict.pop()
                    if len(s_dict) == 0:
                        max_len = max(max_len, i-start+1)
                    else:
                        max_len = max(max_len, i-s_dict[-1])
            i += 1
        return max_len


if __name__ == "__main__":
    answer = Solution()
    print(answer.longestValidParentheses("(())((()"))