題解
我們來分析一下題目，這題的題目很容易理解，本質(zhì)上是一個(gè)尋找字符串最大子串的問題。合法的條件是括號合法，也就是左右括號能夠?qū)ι?。我們之前分析過左右括號的合法條件，其實(shí)很簡單，我們只需要保證右括號出現(xiàn)的數(shù)量一直小于等于左括號的數(shù)量。也就是說((()是有可能合法的，而())是一定不合法的。原因很簡單，因?yàn)槿绻罄ㄌ柕臄?shù)量大于右括號，那么由于后續(xù)還可能會(huì)有括號出現(xiàn)，所以還是有可能構(gòu)成合法的。而反之則不行，所以如果右括號的數(shù)量過多，那么一定不合法。暴力
根據(jù)我們上面分析的結(jié)果，我們不難想出暴力的解法。我們可以枚舉所有的字符串的位置，作為開頭，接著找出從這個(gè)開頭開始可以達(dá)成合法的最大的長度。我們前面說了如果(出現(xiàn)的數(shù)量大于）的時(shí)候，后面仍然可能構(gòu)成合法的匹配，所以我們不能結(jié)束，還需要往下繼續(xù)搜索。而如果）的數(shù)量超過（那后面的就可以不用看了，直接退出即可。如果（的數(shù)量等于），那么說明可以構(gòu)成匹配，我們試著更新答案。我們用代碼實(shí)現(xiàn)這個(gè)邏輯：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++
# 如果已經(jīng)不可能構(gòu)成答案
if r > l:
break
if r == l:
ans = max(ans, 2 * r)
return ans
這段代碼應(yīng)該都能看懂，我們只需要判斷非法和合法兩種情況，如果非法則退出循環(huán)，枚舉下一個(gè)起始位置。如果合法，則試著更新答案。最后，我們返回最大的結(jié)果。這個(gè)暴力的解法當(dāng)然沒問題，但是顯然復(fù)雜度不夠完美，還有很大提升的空間。而且如果這題就這么個(gè)難度，那么也肯定算不上是Hard了。接下來要給大家介紹一種非常巧妙的方法，它不會(huì)涉及許多新的算法和知識點(diǎn)，只是和之前的題目一樣，需要我們對問題有比較深入的理解。尋找模式法
接下來要介紹的這個(gè)方法非常硬核，我們不需要記錄太多的信息，也不會(huì)用到新奇的或者是高端的算法，但是需要我們仔細(xì)分析問題，找到問題的“模式”。我把它稱作是模式匹配算法。其實(shí)模式匹配是專有名詞，我這里只是借用一下。它有些像是正則表達(dá)式，我們寫下一個(gè)模式匹配的規(guī)則，然后正則表達(dá)式引擎就可以根據(jù)我們寫下的模式規(guī)則去尋找匹配的字符串。比如說我們希望找到所有的郵箱，我們約定一個(gè)模式，它接受一個(gè)3到20的字符串，中間必須要存在一個(gè)@符號，然后需要一個(gè)域名作為后綴。我們剛才對于一個(gè)郵箱地址的描述，包括長度、內(nèi)容以及必須存在的字符等等這些要求其實(shí)就是模式。這個(gè)概念有些抽象，但是并不難理解，我相信你們應(yīng)該都能明白。理解了這個(gè)概念之后，我們來思考一個(gè)問題，在這個(gè)問題當(dāng)中，最終長度最大的答案它的模式是什么？我們稍微想一下就可以想明白，不論它多長，它里面的內(nèi)容是什么樣，它應(yīng)該是以(為開頭，以)為結(jié)尾。我們把這個(gè)答案命名為t，我們繼續(xù)來思考，t前面和后面的一個(gè)符號的組合會(huì)是什么樣的？我們列舉一下就能知道，一共只有3種情況，分別是(t(，)t)和)t(。(t)是不可能的，因?yàn)檫@樣可以組成更長的答案，這和我們一開始的假設(shè)矛盾了。所以只有這三種情況。我們來關(guān)注一下)t)和)t(這兩種情況，對于這兩種情況來說，我們可以肯定一點(diǎn)，t前面的)一定不是一個(gè)合法括號的結(jié)尾。答案也很簡單，如果)能夠構(gòu)成合法的括號匹配，那么答案的長度顯然也會(huì)增加。所以它一定是在一個(gè)非法的位置，既然出現(xiàn)在非法的位置，那么我們就可以忽略。換句話說，對于這兩種情況而言，我們只需要遍歷一次字符串，維護(hù)構(gòu)成的合法括號的位置，就一定可以找到它們。原因也很簡單，在我們遍歷到了t前面的)的位置的時(shí)候，由于非法，我們會(huì)將所有記錄的左右括號的信息清除。所以我們一定可以順利地找到t，并且不會(huì)受到其他符號的干擾。但是這樣只能包含兩種情況，對于(t(的情況我們怎么處理呢？因?yàn)槭亲罄ㄌ枺覀儫o法判斷它的出現(xiàn)是否會(huì)產(chǎn)生非法。也就是說我們在遍歷的時(shí)候，無法將t前面的左括號帶來的影響消除。對于這個(gè)問題其實(shí)很簡單，我們只需要反向遍歷即可。由于我們遍歷的順序翻轉(zhuǎn)，所以(成了可能構(gòu)成非法的符號，而)不是，于是就可以識別這一種情況了。我們寫出代碼，真的很簡單，只有兩次遍歷數(shù)組：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
這種方法實(shí)現(xiàn)非常簡單，幾乎毫無難度，效率也很高，是O(n)" role="presentation" style="word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; display: inline; transition: none 0s ease 0s; vertical-align: 0px; line-height: normal; box-sizing: content-box; height: 1px !important; width: 1px !important; overflow: hidden !important;">O(n)的算法，但是需要對問題有很深的思考和理解才行。很多同學(xué)可能會(huì)苦惱，覺得這種方法太取巧了，自己不一定能想得到這么巧妙的方法。沒有關(guān)系，我們接下來會(huì)繼續(xù)介紹一種中規(guī)中矩比較容易想到的方法。dp
接下來要介紹的是鼎鼎大名的dp算法，dp是英文dynamic programming的縮寫，翻譯過來的意思是動(dòng)態(tài)規(guī)劃。它是一個(gè)頻繁出現(xiàn)在各個(gè)算法領(lǐng)域以及面試當(dāng)中的算法，并且應(yīng)用廣泛，在許多問題上用到了動(dòng)態(tài)規(guī)劃的思路，可以說得上是教科書級的算法了。因此對于我們算法學(xué)習(xí)者來說，它也非常的重要。很多初學(xué)者對于動(dòng)態(tài)規(guī)劃可能理解并不深入，不是覺得非常困難，就是還停留在背包問題的范疇當(dāng)中。在這題當(dāng)中，我會(huì)盡可能地講解清楚動(dòng)態(tài)規(guī)劃的內(nèi)在邏輯，以及它運(yùn)行的原理，讓大家真正理解這一算法的思路。至于動(dòng)態(tài)規(guī)劃算法具體的學(xué)習(xí)方法和一些經(jīng)典例題，我們會(huì)放在之后的文章當(dāng)中再詳細(xì)講解。所以如果是沒有基礎(chǔ)的同學(xué)，也不用擔(dān)心，接下來的內(nèi)容也一樣能夠看懂。動(dòng)態(tài)規(guī)劃最樸素的思路就是拆分問題，將大問題拆分成小問題。但是和分治算法不同的是，動(dòng)態(tài)規(guī)劃更加關(guān)注子問題和原問題之間的邏輯聯(lián)系，而分治算法可能更加側(cè)重拆分。并且分治算法的拆分通常是基于數(shù)據(jù)和問題規(guī)模的，而動(dòng)態(tài)規(guī)劃則不然，更加側(cè)重邏輯上的聯(lián)系。除此之外，動(dòng)態(tài)規(guī)劃也非常注重模式的構(gòu)造。如果你看到這里一臉懵逼，啥也沒看明白，沒有關(guān)系，我們用實(shí)際問題來舉例就明白了。我們先來學(xué)一個(gè)技巧，在動(dòng)態(tài)規(guī)劃問題當(dāng)中，我們最經(jīng)常干的一件事情就是創(chuàng)建一個(gè)叫做dp的數(shù)組，它來記錄每一個(gè)位置能夠達(dá)到的最佳結(jié)果。比如在這題當(dāng)中，最佳結(jié)果就是最長匹配的括號串。所以dp[i]就記錄以s[i]結(jié)尾的字符串能夠構(gòu)成的最長的匹配串的長度。那么，我們繼續(xù)分析，假設(shè)當(dāng)前處理的位置i之前的結(jié)果都已經(jīng)存在了，我們怎么通過之前的數(shù)據(jù)獲得當(dāng)前的dp[i]呢？這個(gè)可以認(rèn)為是動(dòng)態(tài)規(guī)劃的精髓，利用之前已經(jīng)存儲(chǔ)的結(jié)果推算當(dāng)前需要求的值。顯然如果s[i]是(，沒什么好說的，以i為結(jié)尾一定不能構(gòu)成合法的串，那么dp[i]=0。也就是說只有s[i]是)的時(shí)候，dp[i]的值才有可能大于0。那么這個(gè)值會(huì)是多少呢？我們繼續(xù)來推算。顯然，我們需要觀察i-1的位置，如果i-1的位置是(，那么說明我們至少可以構(gòu)成一個(gè)match。構(gòu)成這個(gè)match之后呢？其實(shí)就要看dp[i-2]了。因?yàn)樵谝粋€(gè)合法的結(jié)果后面加上一個(gè)括號對顯然也是合法的。所以如果i-1處的結(jié)果是(，那么我們可以得到dp[i] = dp[i-2] + 2。那如果i-1的位置也是)呢？我們來舉個(gè)例子看看就知道了。s: a b ( ) )
idx: i-4 i-3 i-2 i-1 i
從上面這個(gè)例子可以看出來，當(dāng)i-1的位置也是)的時(shí)候，我們可以知道dp[i-1]有可能不為0，那么很簡單，我們只需要跳過dp[i-1]長度的位置就好了。比如上面這個(gè)例子，i-1的位置可以和i-2構(gòu)成match，那么我們就可以跳過dp[i-1]也就是2個(gè)長度，去查看i-3的位置和i是否構(gòu)成match，如果構(gòu)成match，那么最終的答案就是dp[i-1] + 2 + dp[i-4]。因?yàn)閐p[i-4]也有可能還有合法的串。所以，到這里我們就把所有子問題之間的邏輯聯(lián)系都分析清楚了。剩下的就很簡單了，我們只需要根據(jù)上面的分析結(jié)果寫出答案而已。不過還有一點(diǎn)，由于我們一直是利用前面的結(jié)果來推導(dǎo)后面的結(jié)果，我們需要一個(gè)初始的推導(dǎo)基點(diǎn)。這個(gè)基點(diǎn)就是dp[0]，顯然在這個(gè)問題當(dāng)中dp[0]=0。這個(gè)基點(diǎn)有了，剩下的就順理成章了。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也是)，我們需要繼續(xù)往前判斷
# 這里要特別注意下下標(biāo)， 很容易寫錯(cuò)
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
我相信上面的解釋應(yīng)該都能看懂，其實(shí)是很簡單的推理。我相信即使是對dp不太熟悉的同學(xué)，也應(yīng)該都能看懂整個(gè)的運(yùn)行原理。整個(gè)過程同樣是O(n)" role="presentation" style="letter-spacing: 0.544px; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; display: inline; transition: none 0s ease 0s; vertical-align: 0px; line-height: normal; box-sizing: content-box; height: 1px !important; width: 1px !important; overflow: hidden !important;">O(n)的計(jì)算過程，但是和上面的方法相比，我們額外開辟了數(shù)組記錄每個(gè)位置的狀態(tài)。這也是dp算法的特點(diǎn)，就是我們會(huì)存儲(chǔ)幾乎所有中間狀態(tài)的結(jié)果，因?yàn)槲覀冞壿嬯P(guān)系上的推導(dǎo)過程正是基于這些中間狀態(tài)進(jìn)行的。好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。