[LeetCode] 32. Longest Valid Parentheses

Flink_China 發(fā)布于2019-08-19 11:14 / 1633人閱讀

Problem

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 "()()"

Solution DP

class Solution {
    public int longestValidParentheses(String s) {
        //()((()))
        //()()()()
        int max = 0, left = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == "(") left++;
            else {
                if (left != 0) {
                    dp[i] = dp[i-1]+2;
                    if (i-dp[i] >= 0) dp[i] += dp[i-dp[i]];
                    max = Math.max(max, dp[i]);
                    left--;
                }
            }
        }
        return max;
    }
}

Stack

class Solution {
    public int longestValidParentheses(String s) {
        //stack to store index
        Stack stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ")" && !stack.isEmpty() && s.charAt(stack.peek()) == "(") {
                //remove this pair
                stack.pop();
                
                //update the length of this pair
                //
                //if starts with )
                if (!stack.isEmpty()) max = Math.max(max, i-stack.peek());
                //if starts with (
                else max = i+1;
            } else {
                stack.push(i);
            }
        }
        return max;
    }
}

GPU云服務(wù)器云服務(wù)器 Parentheses Longest LeetCode Valid

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77248.html

相關(guān)文章

leetcode32 Longest Valid Parentheses 最長(zhǎng)括號(hào)組的長(zhǎng)度

摘要：題目要求原題地址一個(gè)括號(hào)序列，求出其中成對(duì)括號(hào)的最大長(zhǎng)度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號(hào)序列是否可以成對(duì)。我們可以將堆棧的思路延續(xù)到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。題目要求原題地址：https://leetcode.com/problems... Given a string containing just the c...

happyhuangjinjin 2019-08-14 18:13 評(píng)論0 收藏0
[leetcode]Longest Valid Parentheses

摘要：在問題中，我們可以用來檢驗(yàn)括號(hào)對(duì)，也可以通過來檢驗(yàn)。遇到就加一，遇到就減一。找到一對(duì)括號(hào)就在最終結(jié)果上加。我們用來表示當(dāng)前位置的最長(zhǎng)括號(hào)。括號(hào)之間的關(guān)系有兩種，包含和相離。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

qujian 2019-08-14 16:53 評(píng)論0 收藏0
[Leetcode] Longest Valid Parentheses 最長(zhǎng)有效括號(hào)對(duì)

摘要：假設(shè)是從下標(biāo)開始到字符串結(jié)尾最長(zhǎng)括號(hào)對(duì)長(zhǎng)度，是字符串下標(biāo)為的括號(hào)。如果所有符號(hào)都是，說明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

everfight 2019-08-14 16:11 評(píng)論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評(píng)論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項(xiàng)目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評(píng)論0 收藏0