LeetCode 32，并不Hard的难题，解法超级经典，带你领略动态规划的精彩
TechFlow2019 人气:0本文始发于个人公众号：TechFlow，原创不易，求个关注
今天给大家分享的是LeetCode当中的32题，这是一道Hard难度的题。也是一道经典的字符串处理问题，在接下来的文章当中，我们会详细地解读有关它的三个解法。
希望大家不要被题目上的标记吓到，虽然这题标着难度是Hard，但其实真的不难。我自信你们看完文章之后也一定会这么觉得。
链接
Longest Valid Parentheses
难度
Hard
描述
给定一个只包含左右括号的字符串，返回最长能够组成合法括号的长度
Given a string containing just the characters '(' and ')', find the length
of the longest valid (well-formed) parentheses substring.
样例 1:
Input: "(()"
Output: 2
## Explanation: The longest valid parentheses substring is "()"样例 2:
Input: ")()())"
Output: 4
## Explanation: The longest valid parentheses substring is "()()"思考
我们来分析一下题目，这题的题目很容易理解，本质上是一个寻找字符串最大子串的问题。合法的条件是括号合法，也就是左右括号能够对上。我们之前分析过左右括号的合法条件，其实很简单，我们只需要保证右括号出现的数量一直小于等于左括号的数量。
也就是说((()是有可能合法的，而())是一定不合法的。原因很简单，因为如果左括号的数量大于右括号，那么由于后续还可能会有括号出现，所以还是有可能构成合法的。而反之则不行，所以如果右括号的数量过多，那么一定不合法。
暴力
根据我们上面分析的结果，我们不难想出暴力的解法。我们可以枚举所有的字符串的位置，作为开头，接着找出从这个开头开始可以达成合法的最大的长度。
我们前面说了如果(出现的数量大于）的时候，后面仍然可能构成合法的匹配，所以我们不能结束，还需要往下继续搜索。而如果）的数量超过（那后面的就可以不用看了，直接退出即可。如果（的数量等于），那么说明可以构成匹配，我们试着更新答案。
我们用代码实现这个逻辑：
def brute_force(s):
ans = 0
for i in range(len(s)):
if s[i] == '(':
l = r = 0
for j in range(i, len):
if s[j] == '(':
l++
else:
r++
# 如果已经不可能构成答案
if r > l:
break
if r == l:
ans = max(ans, 2 * r)
return ans这段代码应该都能看懂，我们只需要判断非法和合法两种情况，如果非法则退出循环，枚举下一个起始位置。如果合法，则试着更新答案。最后，我们返回最大的结果。
这个暴力的解法当然没问题，但是显然复杂度不够完美，还有很大提升的空间。而且如果这题就这么个难度，那么也肯定算不上是Hard了。接下来要给大家介绍一种非常巧妙的方法，它不会涉及许多新的算法和知识点，只是和之前的题目一样，需要我们对问题有比较深入的理解。
寻找模式法
接下来要介绍的这个方法非常硬核，我们不需要记录太多的信息，也不会用到新奇的或者是高端的算法，但是需要我们仔细分析问题，找到问题的“模式”。我把它称作是模式匹配算法。
其实模式匹配是专有名词，我这里只是借用一下。它有些像是正则表达式，我们写下一个模式匹配的规则，然后正则表达式引擎就可以根据我们写下的模式规则去寻找匹配的字符串。比如说我们希望找到所有的邮箱，我们约定一个模式，它接受一个3到20的字符串，中间必须要存在一个@符号，然后需要一个域名作为后缀。
我们刚才对于一个邮箱地址的描述，包括长度、内容以及必须存在的字符等等这些要求其实就是模式。这个概念有些抽象，但是并不难理解，我相信你们应该都能明白。理解了这个概念之后，我们来思考一个问题，在这个问题当中，最终长度最大的答案它的模式是什么？我们稍微想一下就可以想明白，不论它多长，它里面的内容是什么样，它应该是以(为开头，以)为结尾。
我们把这个答案命名为t，我们继续来思考，t前面和后面的一个符号的组合会是什么样的？
我们列举一下就能知道，一共只有3种情况，分别是(t(，)t)和)t(。(t)是不可能的，因为这样可以组成更长的答案，这和我们一开始的假设矛盾了。所以只有这三种情况。
我们来关注一下)t)和)t(这两种情况，对于这两种情况来说，我们可以肯定一点，t前面的)一定不是一个合法括号的结尾。答案也很简单，如果)能够构成合法的括号匹配，那么答案的长度显然也会增加。所以它一定是在一个非法的位置，既然出现在非法的位置，那么我们就可以忽略。换句话说，对于这两种情况而言，我们只需要遍历一次字符串，维护构成的合法括号的位置，就一定可以找到它们。
原因也很简单，在我们遍历到了t前面的)的位置的时候，由于非法，我们会将所有记录的左右括号的信息清除。所以我们一定可以顺利地找到t，并且不会受到其他符号的干扰。
但是这样只能包含两种情况，对于(t(的情况我们怎么处理呢？因为是左括号，我们无法判断它的出现是否会产生非法。也就是说我们在遍历的时候，无法将t前面的左括号带来的影响消除。对于这个问题其实很简单，我们只需要反向遍历即可。由于我们遍历的顺序翻转，所以(成了可能构成非法的符号，而)不是，于是就可以识别这一种情况了。
我们写出代码，真的很简单，只有两次遍历数组：
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
l, r = 0, 0
# 正向遍历，寻找)t( 和 )t(两种情况
for i in range(n):
if s[i] == '(':
l += 1
else:
r += 1
if r > l:
l, r = 0, 0
elif r == l:
ans = max(ans, l + r)
l, r = 0, 0
# 反向遍历，寻找(t(这种情况
for i in range(n-1, -1, -1):
# 由于反向遍历，所以非法的判断条件和正向相反
if s[i] == '(':
l += 1
if l > r:
l, r = 0, 0
elif l == r:
ans = max(ans, l+r)
else:
r += 1
return ans这种方法实现非常简单，几乎毫无难度，效率也很高，是\(O(n)\)的算法，但是需要对问题有很深的思考和理解才行。很多同学可能会苦恼，觉得这种方法太取巧了，自己不一定能想得到这么巧妙的方法。没有关系，我们接下来会继续介绍一种中规中矩比较容易想到的方法。
dp
接下来要介绍的是鼎鼎大名的dp算法，dp是英文dynamic programming的缩写，翻译过来的意思是动态规划。它是一个频繁出现在各个算法领域以及面试当中的算法，并且应用广泛，在许多问题上用到了动态规划的思路，可以说得上是教科书级的算法了。因此对于我们算法学习者来说，它也非常的重要。
很多初学者对于动态规划可能理解并不深入，不是觉得非常困难，就是还停留在背包问题的范畴当中。在这题当中，我会尽可能地讲解清楚动态规划的内在逻辑，以及它运行的原理，让大家真正理解这一算法的思路。至于动态规划算法具体的学习方法和一些经典例题，我们会放在之后的文章当中再详细讲解。所以如果是没有基础的同学，也不用担心，接下来的内容也一样能够看懂。
动态规划最朴素的思路就是拆分问题，将大问题拆分成小问题。但是和分治算法不同的是，动态规划更加关注子问题和原问题之间的逻辑联系，而分治算法可能更加侧重拆分。并且分治算法的拆分通常是基于数据和问题规模的，而动态规划则不然，更加侧重逻辑上的联系。除此之外，动态规划也非常注重模式的构造。
如果你看到这里一脸懵逼，啥也没看明白，没有关系，我们用实际问题来举例就明白了。我们先来学一个技巧，在动态规划问题当中，我们最经常干的一件事情就是创建一个叫做dp的数组，它来记录每一个位置能够达到的最佳结果。比如在这题当中，最佳结果就是最长匹配的括号串。所以dp[i]就记录以s[i]结尾的字符串能够构成的最长的匹配串的长度。
那么，我们继续分析，假设当前处理的位置i之前的结果都已经存在了，我们怎么通过之前的数据获得当前的dp[i]呢？这个可以认为是动态规划的精髓，利用之前已经存储的结果推算当前需要求的值。
显然如果s[i]是(，没什么好说的，以i为结尾一定不能构成合法的串，那么dp[i]=0。也就是说只有s[i]是)的时候，dp[i]的值才有可能大于0。那么这个值会是多少呢？我们继续来推算。
显然，我们需要观察i-1的位置，如果i-1的位置是(，那么说明我们至少可以构成一个match。构成这个match之后呢？其实就要看dp[i-2]了。因为在一个合法的结果后面加上一个括号对显然也是合法的。所以如果i-1处的结果是(，那么我们可以得到dp[i] = dp[i-2] + 2。
那如果i-1的位置也是)呢？我们来举个例子看看就知道了。
s: a b ( ) )
idx: i-4 i-3 i-2 i-1 i从上面这个例子可以看出来，当i-1的位置也是)的时候，我们可以知道dp[i-1]有可能不为0，那么很简单，我们只需要跳过dp[i-1]长度的位置就好了。比如上面这个例子，i-1的位置可以和i-2构成match，那么我们就可以跳过dp[i-1]也就是2个长度，去查看i-3的位置和i是否构成match，如果构成match，那么最终的答案就是dp[i-1] + 2 + dp[i-4]。因为dp[i-4]也有可能还有合法的串。
所以，到这里我们就把所有子问题之间的逻辑联系都分析清楚了。剩下的就很简单了，我们只需要根据上面的分析结果写出答案而已。
不过还有一点，由于我们一直是利用前面的结果来推导后面的结果，我们需要一个初始的推导基点。这个基点就是dp[0]，显然在这个问题当中dp[0]=0。这个基点有了，剩下的就顺理成章了。
我们写出代码来看下：
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
dp = [0 for _ in range(n)]
for i in range(1, n):
if s[i] == ')':
# 如果i-1是（，那么我们判断i-2
if s[i-1] == '(':
dp[i] = 2 + (dp[i-2] if i > 1 else 0)
# 如果i-1也是)，我们需要继续往前判断
# 这里要特别注意下下标， 很容易写错
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)
ans = max(ans, dp[i])
return ans我相信上面的解释应该都能看懂，其实是很简单的推理。我相信即使是对dp不太熟悉的同学，也应该都能看懂整个的运行原理。整个过程同样是\(O(n)\)的计算过程，但是和上面的方法相比，我们额外开辟了数组记录每个位置的状态。这也是dp算法的特点，就是我们会存储几乎所有中间状态的结果，因为我们逻辑关系上的推导过程正是基于这些中间状态进行的。
所以这题虽然是Hard，但如果从dp的角度来讲，如果你能想到用dp算法来解决，其实距离解开真的已经不远了。所以不要被题目上标记的Hard吓到，真的没有那么难。另外，我个人也觉得这题将算法的魅力发挥得非常明显，尤其是第二种解法真的非常巧妙。希望大家都能喜欢这题。
今天的文章就是这些，如果觉得有所收获，请顺手扫码点个关注吧，你们的举手之劳对我来说很重要。
加载全部内容