LeetCode 32. Longest Valid Parentheses [Hard] [C++] 解題筆記

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

EX:

        Input: "(()"

        Output: 2

        Explanation: The longest valid parentheses substring is "()"

        Input: ")()())"

        Output: 4

        Explanation: The longest valid parentheses substring is "()()"

想法:

    遇到判定括號的題目基本上都可以用 stack 來解，這題也不例外，我們可以利用一個 stack 來紀錄左括弧在 string 中的位置，

另外利用一個變數 start 來紀錄合法括弧數計算的起始位置。如果當前括弧是 '(' 則將他的位置 push 進 stack 中，若當前括弧是 ')' 且 stack 不為空

可以進行匹配，若匹配完後 stack 為空則表示目前合法的括弧數為( i - start + 1 )，而若 stack 不為空則目前匹合法配數為

( i - stack.back())，而若無法匹配則下次 start 必須從當前位置的下一個位置 (i+1) 開始計算合法括弧數。

    另外這題也可以用 Two Pointer 的方式求解，首先利用 left 與 right 兩個變數分別紀錄 '(' 與 ')' 的數量，若 left == right 表示

合法匹配則更新目前的最大匹配數，若 left < right 表示無法匹配則 left = 0 and right = 0 重新計算。

這裡比較需要注意的是，這種方式必須從左到右且從右到左分別遍歷一次，因為例如 "(()" 的情況只從 左到又右遍歷的話就會忽略最後一個合法的括弧，

同理若只從右到左遍歷在 "())" 的情況也會出錯。

完整程式碼:

Complexity: O(n) time, O(n) space.

解法一(stack):

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> stack;
        int start = 0;
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stack.emplace_back(i);
            }
            else if (stack.size()) {
                stack.pop_back();
                res = stack.empty()? max(res, i - start + 1) : max(res, i - stack.back());
            }
            // stack is empty
            else {
                start = i + 1;
            }
        }
        
        return res;
    }
};

Complexity: O(n) time, O(1) space.

解法二(Two Pointer):

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.size(); i++) {
            (s[i] == '(')? left++ : right++;
            if (left == right) {
                res = max(res, 2 * right);
            }
            if (right > left) {
                left = 0;
                right = 0;
            }
        }
        left = 0;
        right = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            (s[i] == '(')? left++ : right++;
            if (left == right) {
                res = max(res, 2 * right);
            }
            if (right < left) {
                left = 0;
                right = 0;
            }
        }
        
        return res;
    }
};