一魚多吃 用stack來解 最長合法括弧字串 Leetcode #32 Longest Valid Parenthese

這題的題目在這裡:

題目敘述

問我們給定的輸入字串s裡面，最長的合法括弧配對字串長度是多少?

例如 s = "()()" ，最長的合法括弧配對字串長度為4

測試範例

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

約束條件

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

演算法

這題也可以用到前面學過的stack配對模型的模板來實作。

stack底端先push一個-1進去，作為索引哨兵，duumy guard

每次遇到左括號，就推入當下的索引。

每次遇到右括號，就先pop出stack頂端的元素。

假如stack已經空了，代表不匹配，就補推入當下的索引。
假如stack不為空，代表匹配之前的左括號，就計算當下的合法括弧配對字串長度 = 當下索引 - stack頂端的索引。假如比之前的合法括弧配對字串長度還長，就更新過去。

程式碼

class Solution:
　def longestValidParentheses(self, s: str) -> int:

　　# stack, used to record index of parenthesis
　　# initialized to -1 as dummy head for valid parentheses length computation
　　stack = [-1]
　　
　　max_length = 0
　　
		# linear scan each index and character in input string s
　　for cur_idx, char in enumerate(s):
　　　
　　　if char == '(':
　　　　
　　　　# push when current char is (
　　　　stack.append( cur_idx )
　　　　
　　　else:
　　　　
　　　　# pop when current char is )
　　　　stack.pop()
　　　　
　　　　if not stack:
　　　　　
　　　　　# stack is empty, push current index into stack
　　　　　stack.append( cur_idx )
　　　　else:
　　　　　# stack is non-empty, update maximal valid parentheses length
　　　　　max_length = max(max_length, cur_idx - stack[-1])
　　　　
　　return max_length

複雜度分析

時間複雜度: O( n )
從頭到尾，每個字元檢查過一遍。

空間複雜度: O( n )
需要一個stack，stack耗用空間最多和字串長度一樣長。

關鍵知識點

在於理解並且活用stack 先進後出FILO的特質，來實作括號配對。

記得回去複習 合法括號配對這題，主要的原理是相通的。

Reference:

[1] Python/C++/Go O(n) by stack [w/ Comment] - Longest Valid Parentheses - LeetCode