题目
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 "()()"
给出一个只含有 "("、")" 的字符串，寻找字符串中最长的有效括号的长度。
解题思路
这里就需要分析一下 "()" 的特性了：
- "()" 的长度为 2
- ”()“ 左右位置若存在有效括号，则可以进行拼接
- "()" 若有效，且其中间位置存在字符，则中间的字符串也一定为有效括号
依据这三点特性，可以考虑如下思路来寻找最长括号：
- 从左到右遍历字符串，找到有效的括号，并计算其本身的长度
- 以找到 ")" 为 当前标识 ，再寻找与其匹配的 "("，若找到则为有效括号
- 假设当前有效括号中间含有有效括号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])
- 由于是从左到右遍历，所以若左边位置为有效括号（有效括号L），计算最长长度时，需要加上 有效括号L 的长度 max[j-1]
- 计算完 max[i] 与结果容器 res 做较大值比较，赋较大值给 res
- 遍历结束，返回 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] 寻找匹配 "(" 的方式可以同时解决。
代码实现
Runtime: 12 ms
Memory: 20.9 MB
func longestValidParentheses(_ s: String) -> Int {
let len = s.count
// 长度小于 2 的时候，成不了一组 () 所以返回 0
if len < 2 {
return 0
}
// 将 s 转换成数组，方便操作
let s = Array(s)
// max 数组 记录当前有效括号最大长度
var max = Array(repeating: 0, count: len)
// res 作为结果
var res = 0
// 从 1 开始遍历 s
for i in 1 ..< len {
// 只有当前字符为 ")" 时，才有可能出现有效括号
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
}
网友评论