題目

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

給出一個只含有 "("、")" 的字符串，尋找字符串中最長的有效括號的長度。

解題思路

這里就需要分析一下 "()" 的特性了：

1. "()" 的長度為 2
2. ”()“ 左右位置若存在有效括號，則可以進行拼接
3. "()" 若有效，且其中間位置存在字符，則中間的字符串也一定為有效括號

依據(jù)這三點特性，可以考慮如下思路來尋找最長括號：

1. 從左到右遍歷字符串，找到有效的括號，并計算其本身的長度
   • 以找到 ")" 為 當前標識 ，再尋找與其匹配的 "("，若找到則為有效括號
   • 假設當前有效括號中間含有有效括號_M，尋找與其匹配的 "("
     • 找到當前字符 ")" 的位置為 i ，每個有效括號的當前最長長度存進 max[i],
     • 當前位置 i 左移到 有效括號_M 的左側（ 左移 max[i-1] + 1 位），即為當前有效括號的 "(" 的位置 j = i - 1 - max[i-1]
     • 當且僅當位置 j 的字符存在且為 "(" 時，當前有效括號的假設才成功，當前有效括號的長度為當前左右括號長度 2 加上 有效括號_M 的長度 max[i-1]，( 2 + max[i-1])
2. 由于是從左到右遍歷，所以若左邊位置為有效括號（有效括號_L），計算最長長度時，需要加上 有效括號_L 的長度 max[j-1]
3. 計算完 max[i] 與結果容器 res 做較大值比較，賦較大值給 res
4. 遍歷結束，返回 res 即為最長有效括號的長度

PS: 有效括號_M 若存在，其長度為 max[i-1] 有值， 有效括號_M 若不存在 max[i-1] 為 0，若 當前有效括號 中間位置沒有字符時，i-1 位置為 "("，其在max的值max[i-1]也為 0 ，所以 當前有效括號 中間沒有字符時的長度計算方式和 有效括號_M 不存在時的計算方式是一致的，用 j = i - 1 - max[i-1] 尋找匹配 "(" 的方式可以同時解決。

代碼實現(xiàn)

Runtime: 12 ms
Memory: 20.9 MB

func longestValidParentheses(_ s: String) -> Int {
        let len = s.count
        // 長度小于 2 的時候，成不了一組 () 所以返回 0
        if len < 2 {
            return 0
        }
        // 將 s 轉換成數(shù)組，方便操作
        let s = Array(s)
        // max 數(shù)組 記錄當前有效括號最大長度
        var max = Array(repeating: 0, count: len)
        // res 作為結果
        var res = 0
        // 從 1 開始遍歷 s
        for i in 1 ..< len {
            // 只有當前字符為 ")" 時，才有可能出現(xiàn)有效括號
            if s[i] == ")" {
                // 用 i 減去 max[i-1] 的中間位置有效括號長度，再減去當前字符長度 1，即為與當前有效括號的 ( 的位置 j
                let j = i - 1 - max[i-1];
                // 只有當 j >= 0，并且 s[j] 為 ( 時，有效括號才匹配
                if j >= 0 && s[j] == "(" {
                    //有效括號匹配，更新 max[i] 的值，當前成對括號長度 2 ，中間位置有效括號長度 max[i-1]，左側有效括號長度 max[j-1]，加和在一起
                    max[i] = 2 + max[i-1] + (j > 1 ? max[j-1] : 0)
                    //更新較大值到 res
                    res = max[i] > res ? max[i] : res
                }
            }
        }
        return res
    }

代碼地址：https://github.com/sinianshou/EGSwiftLearning