Lintcode423 Valid Parentheses solution 题解
发布在lintcode 题解2018年5月12日view:149
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, determine if the input string is valid.

给定一个字符串所表示的括号序列,包含以下字符: ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, 判定是否是有效的括号序列。

【题目链接】

www.lintcode.com/en/problem/valid-parentheses/

【题目解析】

采用的做法为先将所有合法的独立子串标记出来。这里给定的独立子串,其定义为:

该子串是合法子串,且开头的’(’与’)’是匹配的

举个例子:

”()”,”(()())”,”((())())”,”(()(())())” 都是独立子串。

而”()()”,”(())()”,”()()(())”,虽然都是合法子串,但是它们第一个’(’和最后一个’)’并不是匹配的。并且它们可以再分解为2个合法的独立子串,比如”(())()”可以分解为”(())”和”()”。

我们可以用栈来模拟这个过程,将匹配的括号标记出来。

接下来我们开始寻找最长的合法子串,显然的有最长合法子串一定是由一个或连续多个独立子串构成。

我们再扫描一次整个字符串,将连续的独立子串累加。当出现断开时,将长度重置。

此时累加值最大的连续独立子串就是我们要求得的最长合法子串。

【参考答案】

www.jiuzhang.com/solutions/valid-parentheses/

评论
发表评论
暂无评论
WRITTEN BY
Jennyckx
做个有趣的人(>人<;)
TA的新浪微博
PUBLISHED IN

我的收藏