LeetCode 32，並不Hard的難題，解法超級經典，帶你領略動態規劃的精彩
- 2020 年 3 月 5 日
- 筆記
今天給大家分享的是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
這種方法實現非常簡單，幾乎毫無難度，效率也很高，是的演算法，但是需要對問題有很深的思考和理解才行。很多同學可能會苦惱，覺得這種方法太取巧了，自己不一定能想得到這麼巧妙的方法。沒有關係，我們接下來會繼續介紹一種中規中矩比較容易想到的方法。
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 = [0for _ 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 > 1else0) # 如果i-1也是)，我們需要繼續往前判斷 # 這裡要特別注意下下標， 很容易寫錯 elif i - dp[i-1] > 0and s[i - dp[i-1] - 1] == '(': dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0else0) ans = max(ans, dp[i]) return ans
我相信上面的解釋應該都能看懂，其實是很簡單的推導。我相信即使是對dp不太熟悉的同學，也應該都能看懂整個的運行原理。整個過程同樣是的計算過程，但是和上面的方法相比，我們額外開闢了數組記錄每個位置的狀態。這也是dp演算法的特點，就是我們會存儲幾乎所有中間狀態的結果，因為我們邏輯關係上的推導過程正是基於這些中間狀態進行的。
所以這題雖然是Hard，但如果從dp的角度來講，如果你能想到用dp演算法來解決，其實距離解開真的已經不遠了。所以不要被題目上標記的Hard嚇到，真的沒有那麼難。另外，我個人也覺得這題將演算法的魅力發揮得非常明顯，尤其是第二種解法真的非常巧妙，非常鍛煉思維，希望大家都能喜歡這題。
今天的文章就是這些，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的舉手之勞對我來說很重要。
