【Leetcode-20】

一、题目：

　　给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

　　有效字符串需满足：

　　左括号必须用相同类型的右括号闭合。
　　左括号必须以正确的顺序闭合。

二、代码：

class Solution:
    def isValid(self, s: str) -> bool:
        look_up = {')': '(', '}': '{', ']': '['}
        stack = []
        for item in s:
            if item in look_up.values():
                stack.append(item)
            else:
                if stack and stack[-1] == look_up[item]:
                    stack.pop()
                else:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False

 

一、题目：最长有效括号

　　给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

二、代码：

def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0:
            return 0
        stack = []
        matched = []
        for i, item in enumerate(s):
            if len(stack) > 0 and stack[-1][0] == '(' and item == ')':
                    top_index = stack.pop()
                    matched.append([top_index[1], i])
            else:
                stack.append((item, i))
        if len(matched) == 0:
            return 0
        matched = sorted(matched, key=lambda x: x[0])
        p = matched[0]
        max_len = 0
        for item in matched:
            if item[0] -1 <= p[1]:
                p = [p[0], max(p[1], item[1])]
            else:
                max_len = max(max_len, p[1]-p[0]+1)
                p = item
        max_len = max(max_len, p[1]-p[0]+1)
        return max_len