题目一:

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)

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l = ['0']
        for ch in s:
            if ch == "(" or ch == "[" or ch == "{":
                l.append(ch)
            elif ch == ")":
                if l.pop() != "(":
                    break;
            elif ch == "]":
                if l.pop() != "[":
                    break;
            elif ch == "}":
                if l.pop() != "{":
                    break;
        else:
            if len(l) == 1:
                return True
        return False

题目二:

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个字符处结束的最大匹配串长度，

如果第i个字符为"(":
    则dp[i]肯定为0;
如果第i个字符为")":
    如果第i-1个字符为"("：
        则dp[i] = dp[i - 2] + 2;
    如果第i-1个字符为")“且s[i - dp[i - 1] - 1]为"("：
        则dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

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

代码(python):

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0
        dp = [0 for i in xrange(len(s))]
        for i in xrange(len(s)):
            if s[i] == "(":
                dp[i] = 0
            else: #ch == ")"
                if i - dp[i - 1] -1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0)
                    max_len = max(max_len, dp[i])
        return max_len