題目
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 "()()"
給出一個(gè)只含有 "("意系、")" 的字符串绘搞，尋找字符串中最長(zhǎng)的有效括號(hào)的長(zhǎng)度。
解題思路
這里就需要分析一下 "()" 的特性了：
- "()" 的長(zhǎng)度為 2
- ”()“ 左右位置若存在有效括號(hào)爱态，則可以進(jìn)行拼接
- "()" 若有效，且其中間位置存在字符教届，則中間的字符串也一定為有效括號(hào)
依據(jù)這三點(diǎn)特性栗涂，可以考慮如下思路來尋找最長(zhǎng)括號(hào)：
- 從左到右遍歷字符串苇侵，找到有效的括號(hào)，并計(jì)算其本身的長(zhǎng)度
- 以找到 ")" 為 當(dāng)前標(biāo)識(shí) 历恐，再尋找與其匹配的 "("寸癌，若找到則為有效括號(hào)
- 假設(shè)當(dāng)前有效括號(hào)中間含有有效括號(hào)M，尋找與其匹配的 "("
- 找到當(dāng)前字符 ")" 的位置為 i 弱贼，每個(gè)有效括號(hào)的當(dāng)前最長(zhǎng)長(zhǎng)度存進(jìn) max[i],
- 當(dāng)前位置 i 左移到 有效括號(hào)M 的左側(cè)（ 左移 max[i-1] + 1 位），即為當(dāng)前有效括號(hào)的 "(" 的位置 j = i - 1 - max[i-1]
- 當(dāng)且僅當(dāng)位置 j 的字符存在且為 "(" 時(shí)吮旅，當(dāng)前有效括號(hào)的假設(shè)才成功溪烤，當(dāng)前有效括號(hào)的長(zhǎng)度為當(dāng)前左右括號(hào)長(zhǎng)度 2 加上 有效括號(hào)M 的長(zhǎng)度 max[i-1]，( 2 + max[i-1])
- 由于是從左到右遍歷庇勃，所以若左邊位置為有效括號(hào)（有效括號(hào)L）檬嘀，計(jì)算最長(zhǎng)長(zhǎng)度時(shí)，需要加上 有效括號(hào)L 的長(zhǎng)度 max[j-1]
- 計(jì)算完 max[i] 與結(jié)果容器 res 做較大值比較责嚷，賦較大值給 res
- 遍歷結(jié)束鸳兽，返回 res 即為最長(zhǎng)有效括號(hào)的長(zhǎng)度
PS: 有效括號(hào)M 若存在，其長(zhǎng)度為 max[i-1] 有值再层， 有效括號(hào)M 若不存在 max[i-1] 為 0贸铜，若 當(dāng)前有效括號(hào) 中間位置沒有字符時(shí)堡纬，i-1 位置為 "("，其在max的值max[i-1]也為 0 蒿秦，所以 當(dāng)前有效括號(hào) 中間沒有字符時(shí)的長(zhǎng)度計(jì)算方式和 有效括號(hào)M 不存在時(shí)的計(jì)算方式是一致的烤镐，用 j = i - 1 - max[i-1] 尋找匹配 "(" 的方式可以同時(shí)解決。
代碼實(shí)現(xiàn)
Runtime: 12 ms
Memory: 20.9 MB
func longestValidParentheses(_ s: String) -> Int {
let len = s.count
// 長(zhǎng)度小于 2 的時(shí)候棍鳖，成不了一組 () 所以返回 0
if len < 2 {
return 0
}
// 將 s 轉(zhuǎn)換成數(shù)組炮叶，方便操作
let s = Array(s)
// max 數(shù)組 記錄當(dāng)前有效括號(hào)最大長(zhǎng)度
var max = Array(repeating: 0, count: len)
// res 作為結(jié)果
var res = 0
// 從 1 開始遍歷 s
for i in 1 ..< len {
// 只有當(dāng)前字符為 ")" 時(shí)浑彰，才有可能出現(xiàn)有效括號(hào)
if s[i] == ")" {
// 用 i 減去 max[i-1] 的中間位置有效括號(hào)長(zhǎng)度镀裤，再減去當(dāng)前字符長(zhǎng)度 1，即為與當(dāng)前有效括號(hào)的 ( 的位置 j
let j = i - 1 - max[i-1];
// 只有當(dāng) j >= 0禽绪，并且 s[j] 為 ( 時(shí)医瘫，有效括號(hào)才匹配
if j >= 0 && s[j] == "(" {
//有效括號(hào)匹配侣肄，更新 max[i] 的值，當(dāng)前成對(duì)括號(hào)長(zhǎng)度 2 醇份，中間位置有效括號(hào)長(zhǎng)度 max[i-1]稼锅，左側(cè)有效括號(hào)長(zhǎng)度 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
}
