[LeetCode] 32. Longest Valid Parentheses

轉自LeetCode

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

<Solution>

看到括弧配對的問題，就想到用 stack

那這次複雜一點是，要去算最長的 valid parentheses 長度

想法如下

• stack 存的不是字元，而是該字元的 index，用來找到匹對後，計算長度用

• 因為是要找最長valid parentheses，所以多用一個變數記錄目前最早的合法 index

code 如下
c++

	class Solution {
	public:
	int longestValidParentheses(string s) {
	if(s.empty()) {
	return 0;
	}
	int ans = 0, start = 0;
	stack<int> myStack;
	for(int i = 0; i < s.length(); i++) {
	if(s[i] == '(') {
	myStack.push(i);
	}
	else {
	if(myStack.empty()) {
	//> non-valid parentheses
	start = i+1;
	}
	else {
	myStack.pop();
	ans = myStack.empty() ? max(ans, i - start + 1) : max(ans, i - myStack.top());
	}
	}
	}
	return ans;
	}
	};

view raw longestValidParentheses.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun longestValidParentheses(s: String): Int {
	val stack = mutableListOf<Int>()
	var left = 0
	var ans = 0
	for(right in s.indices) {
	when {
	s[right] == '(' -> stack.add(right)
	stack.isEmpty() -> left = right + 1
	else -> {
	stack.removeAt(stack.lastIndex)
	ans = if(stack.isEmpty()) {
	Math.max(ans, right - left + 1)
	} else {
	Math.max(ans, right - stack.last())
	}
	}
	}
	}
	return ans
	}
	}

view raw longest_valid_parentheses.kt hosted with ❤ by GitHub