有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
越靠后的左括号,最先匹配,也就是 后进先出 的思想,可以用栈这个数据结构
问题描述
给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
例子
思路:
定义两个变量:max_left :将 看着是(。min_left:将 看着是)。
最长有效括号
问题描述
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
思路:
定义一个初始为[-1]的列表res,遍历字符串,碰到( 则将其下标位置记录下来,
每当碰到 ),判断res长度是否>1,
是则说明左边存在(,此时,将res的末尾位置的值j(即(的下标值),求 当前的下标值 - j 与 m的最大值,