1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # stk 用于存储左括号的下标。通过栈来跟踪未匹配的左括号的位置。
        stk = []
        
        # res 用于记录最长有效括号子串的长度
        # l 是当前最长有效括号子串的起始位置
        res, l = 0, 0
        
        # 遍历字符串 s 的每一个字符，r 是当前字符的下标（右指针）
        for r in range(len(s)):
            # 如果当前字符是左括号 '('，将其下标压入栈中
            # 这将帮助我们后续匹配右括号
            if s[r] == '(':
                stk.append(r)
            
            # 如果当前字符是右括号 ')'，并且栈为空，表示没有未匹配的左括号
            # 说明从 l 到 r 的这段字符串无法形成有效括号子串
            # 因此，将 l 更新为 r + 1，表示新的理想起始位置
            elif not stk:
                l = r + 1
            
            # 如果当前字符是右括号 ')'，并且栈不为空，表示有未匹配的左括号
            # 此时，弹出一个左括号的下标，表示这个右括号与最近的左括号匹配成功
            else:
                stk.pop()
                
                # ll 表示当前有效括号子串的起始位置
                # 如果栈为空，表示从 l 到 r 的整个字符串都是有效的
                # 如果栈不为空，表示栈中还有未匹配的左括号
                # 因此有效子串的起始位置是栈顶元素的下一个位置
                ll = stk[-1] + 1 if stk else l
                
                # 更新最长有效括号子串的长度
                # 取当前结果和新的有效子串长度的最大值
                res = max(res, r - ll + 1)
        
        # 最终返回最长有效括号子串的长度
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度
        dp = [0] * len(s)
      
        # 如果字符串为空，直接返回 0
        if not s:
            return 0
      
        # 遍历字符串的每一个字符
        for i in range(len(s)):
            # j 是可能匹配的左括号的位置
            # j = i - 1 - dp[i - 1]，即跳过当前已匹配的子串长度
            j = i - 1 - dp[i - 1]
          
            # 1. 如果当前字符是左括号 '(' 或者 i == 0（第一个字符），跳过
            if i == 0 or s[i] == '(':
                continue
          
            # 2. 如果当前字符是右括号 ')'，且前一个字符是左括号 '('
            # 此时可以直接形成一对有效括号，长度为 2
            # 同时，若 i > 1，还需加上 dp[i-2]（前一个有效子串的长度）
            elif s[i - 1] == '(':
                dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
          
            # 3. 如果当前字符是右括号 ')'，且前一个字符是右括号 ')'
            # 此时需要找到匹配的左括号的位置 j
            # 如果 j < 0，表示没有匹配的左括号，跳过
            elif j < 0:
                continue
          
            # 4. 如果当前字符是右括号 ')'，且 s[j] 是左括号 '('
            # 此时可以形成一对有效括号，长度为 2 + dp[i-1]（中间的有效子串长度）
            # 同时，若 j > 0，还需加上 dp[j-1]（前面的有效子串长度）
            elif s[j] == '(':
                dp[i] = 2 + dp[i - 1] + (dp[j - 1] if j > 0 else 0)
      
        # 返回 dp 数组中的最大值，即最长有效括号子串的长度
        return max(dp) if dp else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = 0  # 最终结果，存储最长有效括号子串的长度
        
        # 第一次扫描：从左到右
        # cnt：计数器，用于记录左括号和右括号的差值
        # l：左指针，表示当前子串的起始位置
        l, r, cnt = 0, 0, 0
        for r in range(len(s)):
            # 每遇到左括号 `(`，cnt += 1；每遇到右括号 `)`，cnt -= 1
            cnt += int(s[r] == '(') - int(s[r] == ')')
            
            # 如果 cnt == 0，说明当前子串是一个有效括号子串
            # 更新结果为当前子串长度 (r - l + 1) 和当前结果中的较大值
            if not cnt:
                res = max(res, r - l + 1)
            
            # 如果 cnt < 0，说明当前子串无效（右括号多于左括号）
            # 重置左指针和计数器
            if cnt < 0:
                l, cnt = r + 1, 0
        
        # 第二次扫描：从右到左
        # cnt：计数器，用于记录右括号和左括号的差值
        # r：右指针，表示当前子串的结束位置
        l, r, cnt = len(s) - 1, len(s) - 1, 0
        for l in range(len(s) - 1, -1, -1):
            # 每遇到右括号 `)`，cnt += 1；每遇到左括号 `(`，cnt -= 1
            cnt += int(s[l] == ')') - int(s[l] == '(')
            
            # 如果 cnt == 0，说明当前子串是一个有效括号子串
            # 更新结果为当前子串长度 (r - l + 1) 和当前结果中的较大值
            if not cnt:
                res = max(res, r - l + 1)
            
            # 如果 cnt < 0，说明当前子串无效（左括号多于右括号）
            # 重置右指针和计数器
            if cnt < 0:
                r, cnt = l - 1, 0
        
        return res