如何使用java找出最長有效括號

如何使用Java找出最長有效括號

在編程面試中，經常會遇到與字符串處理相關的問題。其中一個經典的問題是：如何找出字符串中最長的有效括號子串。有效括號子串是指由成對的括號組成的子串，且這些括號是正確匹配的。本文將詳細介紹如何使用Java來解決這個問題，并提供相應的代碼示例。

問題描述

給定一個只包含字符 '(' 和 ')' 的字符串 s，找出其中最長的有效（格式正確且連續）括號子串的長度。

示例 1:

輸入: s = "(()"
輸出: 2
解釋: 最長有效括號子串是 "()"

示例 2:

輸入: s = ")()())"
輸出: 4
解釋: 最長有效括號子串是 "()()"

示例 3:

輸入: s = ""
輸出: 0

解題思路

要解決這個問題，我們可以使用動態規劃或棧的方法。本文將重點介紹使用棧的解法，因為這種方法相對直觀且易于理解。

使用棧的解法

棧是一種后進先出（LIFO）的數據結構，非常適合用來處理括號匹配的問題。我們可以通過棧來記錄每個字符的索引，從而計算出最長的有效括號子串。

算法步驟

1. 初始化棧：我們首先在棧中壓入一個初始值 -1，這樣可以方便地計算有效括號的長度。
2. 遍歷字符串：從左到右遍歷字符串中的每個字符。
   • 如果當前字符是 '('，將其索引壓入棧中。
   • 如果當前字符是 ')'，彈出棧頂元素。如果棧為空，說明當前 ')' 沒有匹配的 '('，因此將當前索引壓入棧中。否則，計算當前有效括號的長度，并更新最大長度。
3. 返回結果：遍歷結束后，返回記錄的最大長度。

代碼實現

import java.util.Stack;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 初始化棧

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i); // 壓入當前索引
            } else {
                stack.pop(); // 彈出棧頂元素
                if (stack.isEmpty()) {
                    stack.push(i); // 如果棧為空，壓入當前索引
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek()); // 計算當前有效括號長度
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestValidParentheses solution = new LongestValidParentheses();
        System.out.println(solution.longestValidParentheses("(()")); // 輸出: 2
        System.out.println(solution.longestValidParentheses(")()())")); // 輸出: 4
        System.out.println(solution.longestValidParentheses("")); // 輸出: 0
    }
}

復雜度分析

• 時間復雜度：O(n)，其中 n 是字符串的長度。我們只需要遍歷字符串一次。
• 空間復雜度：O(n)，在最壞情況下，棧的大小可能達到 n。

動態規劃解法（簡要介紹）

除了棧的解法，我們還可以使用動態規劃來解決這個問題。動態規劃的思路是定義一個數組 dp，其中 dp[i] 表示以第 i 個字符結尾的最長有效括號子串的長度。通過狀態轉移方程，我們可以逐步計算出每個位置的最長有效括號長度。

狀態轉移方程

• 如果 s[i] == ')' 且 s[i-1] == '('，則 dp[i] = dp[i-2] + 2。
• 如果 s[i] == ')' 且 s[i-1] == ')'，并且 s[i - dp[i-1] - 1] == '('，則 dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。

代碼實現

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestValidParentheses solution = new LongestValidParentheses();
        System.out.println(solution.longestValidParentheses("(()")); // 輸出: 2
        System.out.println(solution.longestValidParentheses(")()())")); // 輸出: 4
        System.out.println(solution.longestValidParentheses("")); // 輸出: 0
    }
}

總結

本文介紹了如何使用Java找出字符串中最長的有效括號子串。我們重點講解了使用棧的解法，并簡要介紹了動態規劃的解法。棧的解法相對直觀且易于實現，適合在面試中快速解決問題。希望本文能幫助你更好地理解和掌握這一經典算法問題。