LeetCode #32 Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

在旅行的過程中嘗試解這一題，剛開始第一直覺便想到可以使用 stack 來處理，利用 stack 先進先出的特性，來模擬先輸入 (，然後再輸入個 ) 時，利用 peek 來看是否有合用的 ( 來組成一組並且 pop，持續進行最後能找到結果，後來實作幾個版本後都無法滿足 test cases，後來重新思考想到一個簡單的解決方案……。

分析

計算輸入字串中，最長合法的括弧字串長度，例如輸入字串 ()((())，要能夠輸出 4。

有效的括弧，不外乎是 ( 與 ) 兩兩配對，即使使巢狀的括弧，例如 (())，也會都是兩兩的配對。

利用這個條件，思考可以重新編碼字串，讓兩個配對的左右括弧編碼成 .，例如輸入字串 ()))(())，編碼成 .))..。如此一來只要找尋最長使用 . 組成的子字串長度，那便會是想要的答案。

因此利用上述思考其演算法，可使用 stack 先進先出的概念處理資料 (雖然實作上不是正統的 stack)，其演算法：

• 逐一列舉字串字元，用到左括號 (，一律直接 push 到 stack 中
• 遇到右括號 )，stack 持續 pop，若遇到 (，則合併成 .，並且再 push 回 statck 中
• 若 stack pop 遇到 . 則不管，因為那是合法的括號規則
• 若發現 stack pop 到 empty，表示該右括號沒有對應的左括號，原先 pop 的資料依序在 push 回 stack 中，之後再將該右括號也 push 進 stack
• 若 stack pop 遇到相同的右括號，那麼停止檢查，因為沒有合法的括號規則。此外相同的，原先 pop 的資料依序在 push 回 stack 中，之後再將該右括號也 push 進 stack
• 反覆執行直到列舉完畢
• 最後根據 stack 內容，找到最長合法的括號長度 (. 組成的子字串)

若輸入字串為 ()))(())，其資料圖解：

解法

使用 Go：

func longestValidParentheses(s string) int {
   // Encode parentheses by validing rules
   q := make([]rune, 0, len(s))
   for _, c := range s {
      if c == '(' {
         q = append(q, c)
      } else if c == ')' {
         q = append(q, c)
      L:
         for i := len(q) - 2; i >= 0; i-- {
            switch q[i] {
            case '(':
               q[i] = '.'
               q = q[:len(q)-1]
               break L
            case ')':
               break L
            }
         }
      }
   }
   
   // Find longest ... substring
   max := 0
   cur := 0
   for _, c := range q {
      if c == '.' {
         cur += 1
         if cur > max {
            max = cur
         }
      } else {
         cur = 0
      }
   }
   return max * 2
}

不過看過其他人的解法後，可以直接修改改用 index 操作，這樣就不用進行編碼再計算合法括號的長度了……。