阿里二面演算法題
最長的括弧子串
問題描述
給出一個長度為 n 的，僅包含字元 ‘(‘ 和 ‘)’ 的字元串，計算最長的格式正確的括弧子串的長度。
示例：
輸入：”(())”
輸出：4
解析：對於”(())”來說，最長格式正確的子串是”(())”，所以為4。
分析問題
對於括弧匹配問題，最直觀的想法就是採用棧來求解。所以，我們也可以採用棧來求解這道題。具體來說，我們在遍歷給定字元串的過程中，需要始終保證棧底元素為當前已經遍歷過的元素中，最後一個沒有被匹配的右括弧的下標，棧中的其它元素維護左括弧的下標。
- 如果遇到的是左括弧『（』，我們就把它的下標放入棧中；
- 如果遇到的是右括弧『）』，此時有兩種情況；
- 如果此時棧為空，說明當前的右括弧是沒有被匹配的右括弧，
- 如果此時棧不為空，右括弧的下標減去棧頂元素即為「以該右括弧為結尾的最長有效括弧的長度」，然後用它來更新最大值即可。
這裡需要注意一點，因為一開始棧為空，如果此時第一個字元為左括弧時，我們會將其對應的下標放入棧中，這樣就不滿足棧底始終保存的是最後一個沒有被匹配的右括弧的下標這個條件，為了保證該條件成立，我們在開始時需要往棧中放入一個元素-1。
我們以「())(())」為例，來看一下執行過程。
下面我們來看一下程式碼實現。
class Solution(object):
def longestValidParentheses(self, s):
stack=[]
n=len(s)
stack.append(-1)
maxlen=0
for i in range(0,n):
#如果是左括弧，將其對應的下標加入棧中
if s[i]=='(':
stack.append(i)
else:
#如果是右括弧，棧頂元素pop出去
stack.pop()
if not stack:
stack.append(i)
else:
maxlen = max(maxlen, i - stack[-1])
return maxlen
該演算法的時間複雜度和空間複雜度都是O(n)。
動態規劃解法
對於求最優解問題，我們一般首先需要考慮的就是動態規劃的解法。顯然，求最長的括弧子串是最優解問題，所有我們也可以採用動態規劃的思想來求解。
首先我們定義dp[i]表示以下標i字元結尾的最長有效括弧的長度，初始時數組dp全為0。對於有效的括弧子串來說，顯然是以字元『）』結尾的，因此我們可以知道以『（』結尾的子串對應的dp值必然為0，所以我們只需要求解字元『）』在dp數組中對應位置的值即可。
我們從前往後遍歷字元串s。
-
如果s[i]=『）』且 s[i-1]=『（』，也就是字元串是 「….()….()….」的形式，那麼我們可以得出狀態轉移方程為dp[i] = dp[i-2] + 2。
-
如果s[i]=『）』且 s[i-1]=『）』，也就是字元串是「………))…」的形式，此時如果s[i-dp[i-1]-1] = 『（』，那麼
dp[i] = dp[i-1] + 2 + dp[i – dp[i-1] – 2]
解釋：如果 s[i-1] 對應的 『）』 是有效子字元串的一部分，我們假設為sub1，那麼它的的長度為dp[i-1]，如果s[i]對應的『）』是一個更長子字元串的一部分，那麼一定有一個對應的『（』與子相匹配，且它的位置在sub1的之前。如果sub1的前面恰好是『（』，即「 (sub1) 」的形式，那麼dp[i]=dp[i-1] + 2 + dp[i-dp[i-1] – 2] ，其中dp[i-dp[i-1] – 2] 表示字元串「(sub1)」前面的有效子串的長度，我們需要加上。
下面我們來看一下程式碼的實現。
class Solution(object):
def longestValidParentheses(self, s):
maxlen=0
n=len(s)
dp=[0] * n
for i in range(1,n):
#如果s[i]==')'並且s[i-1]=='(',那麼dp[i] = dp[i-2]+2
if s[i]==')':
if s[i-1]=='(':
dp[i] = 2 + (dp[i-2] if i>=2 else 0)
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]=='(':
dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i-dp[i-1]>=2 else 0)
maxlen=max(maxlen,dp[i])
return maxlen
該演算法的時間複雜度是O(n)，空間複雜度也是O(n)。
