Skip to content

LeetCode: 32-Longest Valid Parentheses 解題紀錄

Last Updated on 2021-02-04 by Clay

題目

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

Example:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

這個題目輸入一個只由 '(' 或是 ')' 組成的字串，而我們要做的，就是判斷最長的『合理』子字串長度。

比方說， "()" 就是合理的子字串、")(" 就是個不合理的子字串。

解題思路

最初，我直接將字串從左讀到右，看最長的合理字串為何，並在右括號 ')' 大於左括號 '(' 時還原紀錄的最長長度；然而這個方法很快地被破解。

為了解決這個問題，我改從字串右讀到左 —— 依此類推，然而被跟上述方法很像的輸入所破解。

然後我想通了，我應該從右到左讀一遍、然後再從左讀到右，最後決定最長的長度。


C++ 程式碼

class Solution {
public:
    int longestValidParentheses(string s) {
        // Init
        int max_len = 0;
        int left = 0;
        int right = 0;
        
        // Left to right
        for (int i=0; i<s.size(); ++i) {            
            if (s[i] == '(') {
                ++left;
            }
            else {
                ++right;
            }
            
            if (left == right) {
                max_len = max(max_len, left+right);
            }
            else if (left < right) {
                left = 0;
                right = 0;
            }
        }
        
        // Init
        left = 0;
        right = 0;
        
        // Right to left
        for (int i=s.size()-1; i>=0; --i) {
            if (s[i] == ')') {
                ++right;
            }
            else {
                ++left;
            }
            
            if (left == right) {
                max_len = max(max_len, left+right);
            }
            else if (left > right) {
                left = 0;
                right = 0;
            }
        }
        
        return max_len;
    }
};


Python 程式碼

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Init
        max_len = 0
        left = 0
        right = 0
        
        # Left to right
        for w in s:
            if w == '(':
                left += 1
            else:
                right += 1
            
            if left == right:
                max_len = max(max_len, left+right)
            elif left < right:
                left = 0
                right = 0
        
        # Init
        left = 0
        right = 0
        
        # Right to left
        for w in reversed(s):
            if w == ')':
                right += 1
            else:
                left += 1
            
            if left == right:
                max_len = max(max_len, left+right)
            elif left > right:
                left = 0
                right = 0
        
        return max_len


References

Tags:

Leave a Reply