32.leetcode题目讲解(Python):最长的有效括号(更新动态规划解法)

题目:

最长的有效括号

解法1:栈实现

通过使用栈来实现。遍历字符串,如果字符等于 “(“,将该字符的索引放入栈中。如果字符等于”)”,首先判断栈是否为空,若为空,直接将其索引放入栈中。如果栈不为空,那查看栈顶元素是否为 “(“,如果是,进行pop()操作,当前长度等于 当前 “)” 的索引减去pop()操作后的栈顶元素(如果pop()后栈为空,那么当前长度等于索引+1)。

特别注意:栈是否为空

参考代码如下:

解法2:动态规划

解法2:动态规划(待更新)
动态规划的思路是,我们用一个list:dp 来记录字符串s中第i个元素的有效匹配长度。
当前字符为“)”时,才有可能出现匹配,所以我们关注两种情况:“()”和“))”
1. “()”:

  1. “))”:

完整代码如下:

—————————————

如果您有好的建议,欢迎来信与我交流
邮箱
也欢迎关注微信公众号“苔原带”
邮箱