LeetCode第20/32题:Valid Parentheses和Longest Valid Parentheses 总结

题目一:

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

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

  • 大意:给定一个字符串,只包含”(){}[]”这些字符,判断字符串的括号是否都匹配。

思路

显然是用栈的思想做。

代码

(Python)

题目二:

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

  • 大意:给定一个只包含”(“或者”)”的字符串,判断最长的有效括号对,返回长度。比如:”)()())”的最长有效括号对为,”()()”,长度为4。

思路

DP的思路:dp[i]代表第i个字符处结束的最大匹配串长度,

参考:
《My DP, O(n) solution without using stack》( https://leetcode.com/discuss/8092/my-dp-o-n-solution-without-using-stack )

代码(python):

发表评论

电子邮件地址不会被公开。 必填项已用*标注