【LeetCode】032. Longest Valid Parentheses

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



Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is `"()"`



Example 2:

Input: "`)()())`"
Output: 4
Explanation: The longest valid parentheses substring is `"()()"`


解題邏輯與實作

這題算是Valid Parentheses的進階版,不過還是可以用Stack來解決。


Stack

由於我需要知道知道它們之間的距離,所以推入stack時我除了紀錄括號外,也紀錄他們的索引值。

  1. 開始前先push ( -1, ‘)’ )進入stack
  2. 依序讀入字串
    1. 若遇到左括號,push (index , ‘(’ )
    2. 若遇到右括號,則檢查stack最上層
      1. 若為右括號,push (index , ‘)’ )
      2. 若為左括號,將其pop並檢查長度,檢查方式為:使用目前索引值減掉目前最上層的索引值後,與目前所紀錄的最長合法長度取max。



程式碼

from pythonds.basic.stack import Stack 
class Solution:
	def longestValidParentheses(self, s):
		max_valid = 0
		stack = Stack()
		stack.push((-1,')'))
		for i, char in enumerate(s) :
			if char == '(':
				stack.push((i,char))
			else:
				if stack.peek()[1] == ")" :
					stack.push((i,char))
				else:
					stack.pop()
					max_valid = max(max_valid, i - stack.peek()[0]) 

		return max_valid


Dynamic Programming

Po文前打Tag時才發現,這題的標籤是DP反而沒有Stack耶~!
所以…我逃避現實先,之後再來補好了…是說我欠了多少題的DP解了?

DP 參考作法 -> 傳送門



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

用Markdown寫Blogger文章

【Vue.js 學習筆記】02. 基礎 Vue 概述