leetcode32：最长有效括号

题目链接

leetcode

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

C++ 代码

// 32. 最长有效括号

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

/*
    栈中维护当前待匹配的左括号的位置，start 记录一个新的合法子串的起始位置。
    1.遇到左括号，当前位置进栈。
    2.遇到右括号，若栈不空，则栈顶出栈。
        若栈为空，说明当前右括号没有匹配的左括号，将其索引作为新的起始位置。
        若栈不为空，计算当前有效括号的长度，并更新最大长度。
    3.遇到右括号并且栈为空，
        说明当前的右括号没有与之匹配的左括号，它是一个无效序列的开始。
        下一个合法子串的起始位置是 i + 1，更新 start = i + 1。

    时间复杂度：O(n)
        n 是字符串的长度。只需要遍历字符串一次。
    空间复杂度：O(n)
        在最坏情况下，栈的大小会达到 n。
*/
class Solution_0 {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0, start = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                if (!stk.empty()) {
                    stk.pop();
                    if (stk.empty()) {
                        res = max(res, i - start + 1);
                    } else {
                        res = max(res, i - stk.top());
                    }
                } else {
                    start = i + 1;
                }
            }
        }

        return res;
    }
};

/*
    状态表示：
        dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。
    状态计算：
        1. s[i] = ')' 且 s[i−1] = '('
            即字符串如 "...()"
            dp[i] = dp[i−2] + 2
        2. s[i] = ')' 且 s[i−1] = ')'，s[i−dp[i−1]−1] = '(
            即字符串如 "...))"
            dp[i] = dp[i−1] + 2 + dp[i−dp[i−1]−2]
    初始化：
        初始化为 0，因为默认情况下，没有有效括号子串。
    遍历顺序：
        从前往后遍历字符串求解 dp 值，每次检查相邻的两个字符。
    答案：dp 数组中的最大值。

   时间复杂度：O(n)
       其中 n 为字符串的长度。
       遍历整个字符串一次，求出 dp 数组。
   空间复杂度：O(n)
       需要一个大小为 n 的数组。
*/
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), res = 0;
        vector<int> f(n, 0);
        for (int i = 1; i < n; i ++) {
            if (s[i] == ')') {
                if (s[i-1] == '(') {
                    f[i] = (i >= 2 ? f[i - 2] : 0) + 2;
                } else if (i-f[i-1] > 0 && s[i-f[i-1]-1] == '(') {
                    f[i] = f[i-1] + (i-f[i-1] >= 2 ? f[i-f[i-1]-2] : 0) + 2;
                }
                res = max(res, f[i]);
             }
        }
        
        return res;
    }
};

int main() {
    Solution solution;
    vector<string> test_cases = {
        "(()",
        ")()())",
        ""
    };

    for (auto& str : test_cases) {
        cout << "Input: " << str << endl;
        cout << "Output: " << solution.longestValidParentheses(str) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   栈的使用：
       使用一个栈存储索引，栈顶始终存储当前有效括号的起始位置。
       初始化栈时，加入一个虚拟的起始位置 -1，方便处理边界情况。
   遍历字符串：
       遇到左括号 (，直接入栈。
       遇到右括号 )，弹出栈顶：
       如果栈为空，说明当前右括号没有匹配的左括号，将其索引作为新的起始位置。
       如果栈不为空，计算当前有效括号的长度，并更新最大长度。
   返回结果：
       遍历结束后，返回最大长度。

   时间复杂度：O(n)
       遍历一次字符串，时间复杂度为 O(n)，其中 n 是字符串的长度。
   空间复杂度：O(n)
       使用了一个栈存储索引，空间复杂度为 O(n)。
*/
// longestValidParentheses 返回最长的包含有效括号的子字符串的长度
func longestValidParentheses(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }

    stack := make([]int, 0) // 存储索引的栈
    stack = append(stack, -1) // 初始化栈，添加一个哨兵值
    maxLen := 0 // 记录最长有效括号长度
    for i, c := range s {
        // 遇到左括号，直接入栈
        if c == '(' {
            stack = append(stack, i)
        } else {
            // 遇到右括号，弹出栈顶元素
            stack = stack[:len(stack)-1]
            // 如果栈为空，说明当前右括号无法匹配，将索引入栈作为新的哨兵
            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                // 如果栈不为空，说明当前右括号可以匹配，计算有效括号的长度
                maxLen = max(maxLen, i-stack[len(stack)-1])
            }
        }
    }

    return maxLen
}

/*
    状态表示：
        dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。
    状态计算：
        1. s[i] = ')' 且 s[i−1] = '('
            即字符串如 "...()"
            dp[i] = dp[i−2] + 2
        2. s[i] = ')' 且 s[i−1] = ')'，s[i−dp[i−1]−1] = '(
            即字符串如 "...))"
            dp[i] = dp[i−1] + 2 + dp[i−dp[i−1]−2]
    初始化：
        初始化为 0，因为默认情况下，没有有效括号子串。
    遍历顺序：
        从前往后遍历字符串求解 dp 值，每次检查相邻的两个字符。
    答案：dp 数组中的最大值。

   时间复杂度：O(n)
       其中 n 为字符串的长度。
       遍历整个字符串一次，求出 dp 数组。
   空间复杂度：O(n)
       需要一个大小为 n 的数组。
*/
func longestValidParentheses_1(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }

    // dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度
    dp := make([]int, n) 
    maxLen := 0
    // 状态计算
    for i := 1; i < n; i ++ {
        if s[i] == ')' {
            if s[i-1] == '(' {
                // 如果当前字符是 ')'，并且前一个字符是 '('，则形成一对有效括号
                dp[i] = 2
                if i >= 2 {
                    dp[i] += dp[i-2] // 加上前一个有效括号子串的长度
                }
            } else if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
                // 如果当前字符是 ')'，并且前一个有效括号子串的前一个字符是 '('
                dp[i] = dp[i-1] + 2
                if i-dp[i-1]-2 >= 0 {
                    dp[i] += dp[i-dp[i-1]-2] // 加上前一个有效括号子串的长度
                }
            }
            // 更新最长有效括号子串的长度
            maxLen = max(maxLen, dp[i])
        }
    }
    return maxLen
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		expected int
	}{
		{
			s:        "(()",
			expected: 2,
		},
		{
			s:        ")()())",
			expected: 4,
		},
		{
			s:        "",
			expected: 0,
		},
	}

	for i, tc := range testCases {
		result := longestValidParentheses(tc.s)
		fmt.Printf("Test Case %d, Input: s = %q\n", i+1, tc.s)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}