問(wèn)題描述

* 找出字符串中最長(zhǎng)的有效子串，字符串只包括'(' , ')'。何為有效，可參考leetcode20 判斷一個(gè)字符串是否為有效字符串。

解題思路

介紹動(dòng)態(tài)規(guī)劃的解法

從倒數(shù)第二個(gè)元素往前遍歷，特別針對(duì) " ( ) " 的情況。

用一維數(shù)組保存結(jié)果,d[i] 代表從當(dāng)前下標(biāo) i 到字符串 s 最末尾的子串中的最長(zhǎng)有效子串的長(zhǎng)度。

動(dòng)態(tài)方程如何寫呢？

對(duì)于當(dāng)前下標(biāo)i，如果是 ' ( '，則考慮右邊子串中的元素，是否為 ' )'?？紤]哪一個(gè)呢？ symi 變量是怎么想到的呢？后來(lái)我思考發(fā)現(xiàn)，發(fā)現(xiàn)原作設(shè)置的 symi 變量確實(shí)巧妙。symi 代表對(duì)于當(dāng)前下標(biāo)i，需要進(jìn)行匹配的右括號(hào)的位置。此時(shí)若是匹配，則得到的 d[i] 代表從 i 到 symi 之間的子串的最長(zhǎng)有效子串長(zhǎng)度，如果下標(biāo) symi 右邊還有元素。則需要加上 d[symi+1]。

1 public class Solution { 2 public int longestValidParentheses(String s) { 3 if(null == s) return 0; 4 int len = s.length(), max = 0; 5 int[] d = new int[len]; 6 for (int i = len-2; i >= 0; i--){ 7 int symi = i+1+d[i+1]; 8 if ('(' == s.charAt(i) && symi < len && ')' == s.charAt(symi)){ 9 // 如果滿足條件，則相當(dāng)于在d[i+1]的基礎(chǔ)上又多了一對(duì)"（）"，所以長(zhǎng)度+2 10 d[i] = d[i+1]+2; 11 // 如果symi右邊還有元素，那么d[i]就應(yīng)該加上d[symi+1] 12 if(symi+1 < len){ 13 d[i] += d[symi+1]; 14 } 15 } 16 max = Math.max(max, d[i]); 17 } 18 return max; 19 } 20 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/dogeLife/p/11000444.html

總結(jié)

以上是生活随笔為你收集整理的leetcode32 Longest Valid Parentheses的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。