【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能力,本题最优解还是用栈比较好

Comments
登录后评论
Sign In