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