【Python】括号匹配问题

括号生成问题（leetcode 22）

思路：

• 确定使用递归
• 确定递归剪枝条件：
  • 当左括号left大于n时，非法，剪枝
  • 当右括号right比左括号left多时，非法，剪枝
• 对于获得排列组合题，构建集合，递归函数带上路径path
• 路径就加个左括号，left就++，加个右括号right就++

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = set()
        self.dfs(n, 0, 0, "", res)
        return list(res)

    def dfs(self, n, left, right, path, res):
        if left > n or right > left:
            return 
        if len(path) == n * 2:
            res.add(path)
            return
        self.dfs(n, left+1, right, path+"(", res)
        self.dfs(n, left, right+1, path+")", res)

最长有效括号（leetcode 32）

妈呀，这是我在面试华为的时候，出的一道题。

当时用栈做出来了，现在试试DP，逆天的DP，脑子不够用了

DP思路：

• 先对s进行基本的修正，左边为)的不可能匹配成功，右边为(不能匹配成功，直接strip掉
• 边界条件返回0
• 构建dp，dp[0]肯定为0，从1开始遍历
• 判断s[i]为(的情况，匹配失败dp[i] = 0
• 判断s[i]为)的情况:
  • 如果 i >= 1 并且 s[i-1] == "("，匹配成功，如果 i == 1, dp[i-2] -> dp[-1] == 0
  • i == 0 or s[i-1] == ")"的情况，i==0时，dp[0]=0，不管； 剩下s[i-1] == ")"的情况，注意 i - dp[i-1] > 0即确定与s[i]对应的"("存在，且为"("，即可得出 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]

举个栗子🌰："()(())"，i指向5时，dp[i-dp[i-1]-2] -> dp[5-2-2] == dp[1] == 2，"(())"，i指向3时，dp[i-dp[i-1]-2] -> dp[-1] == 0

PS: dp[i-dp[i-1]-2]在这种情况下，可能存在也可能不存在，不存在则为 dp[-1] = 0，没有赋值就是0，存在就直接加

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        s = s.lstrip(")").rstrip("(")
        if len(s) == 0:
            return 0
        dp = [0 for _ in range(len(s))]
        for i in range(1, len(s)):
            # if s[i] == '(': dp[i] = 0    # 以(结尾非法，dp初始化就为0，可以省略
            if s[i] == ')':  # 如果为右括号，左边匹配成功且i>=2，dp依赖
                if i >= 1 and s[i-1] == '(':
                    dp[i] = dp[i-2] + 2
                else:  # 如果匹配不成功，i - dp[i-1]为s[i]的左括号位置（如果有的话）
                    if i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
                        dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
        return max(dp)

再次强调：第二题DP仅用于锻炼DP能力，本题最优解还是用栈比较好