[leetcode]032-Longest Valid Parentheses[动态规划]

本文主要是介绍[leetcode]032-Longest Valid Parentheses[动态规划]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 原题

https://leetcode.com/problems/longest-valid-parentheses/submissions/

2. 思路

题意：给出一串由括号组成的字符串，求出最长匹配的子串

思路：比较难。容易想到的方法就是遍历字符串。利用栈的思想，找出匹配的括号位置，

不断更新匹配长度。

另外的方法就是动态规划了。dp[i]表示以下标i结尾时的最长长度。

假如当前位置i，若s[i] = '(', 显然dp[i]= 0;

若s[i] = ')', 我们要看看i-dp[i-1]-1处是不是'(', 不是说明不匹配，dp[i]= 0;

否则，匹配。注意：判断的位置不是i-1, 而是i-dp[i-1]-1。 因为可能存在'(()'这种情况。

匹配成功，dp[i] = dp[i-1]+2。 不过没完，dp[i]还要加上dp[i-dp[i]].

因为之前的长度被'('中断了，还要补上。

3. 源码

class Solution:def longestValidParentheses(self, s: str) -> int:dp = [0] * len(s) #初始值都是0res = 0for i in range(1, len(s)):if s[i] == ')' and i-1 >= dp[i-1] and s[i-dp[i-1]-1] == '(':dp[i] = dp[i-1]+2 #匹配成功if i >= dp[i]:dp[i] += dp[i-dp[i]] #还要加上之前的res = max(res, dp[i])return res

 

这篇关于[leetcode]032-Longest Valid Parentheses[动态规划]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---