給定一個(gè)字符串s，其中只包含字符'('和')'，需要找出其中最長的有效括號(hào)子串的長度。本篇文章將介紹如何通過動(dòng)態(tài)規(guī)劃算法來實(shí)現(xiàn)這一目標(biāo)。 實(shí)現(xiàn)算法步驟 創(chuàng)建一個(gè)數(shù)組dp，其中第i個(gè)元素表示

給定一個(gè)字符串s，其中只包含字符'('和')'，需要找出其中最長的有效括號(hào)子串的長度。本篇文章將介紹如何通過動(dòng)態(tài)規(guī)劃算法來實(shí)現(xiàn)這一目標(biāo)。

實(shí)現(xiàn)算法步驟

1. 創(chuàng)建一個(gè)數(shù)組dp，其中第i個(gè)元素表示字符串s中第i個(gè)字符對(duì)應(yīng)的有效括號(hào)長度。
2. 通過動(dòng)態(tài)規(guī)劃思想，填充上述dp數(shù)組：
   • 如果s[i]')'且s[i-1]'('，即括號(hào)串的樣式為"(...)"，則dp[i]dp[i-2] 2。
   • 如果s[i]')'且s[i-1]')'，即括號(hào)串形如"...)..."，如果s[i-dp[i-1]-1]'('，那么dp[i]dp[i-1] dp[i-dp[i-1]-2] 2。

編寫本地測(cè)試主方法

為了驗(yàn)證算法的正確性，可以編寫一個(gè)本地測(cè)試方法來觀察控制臺(tái)輸出結(jié)果是否符合預(yù)期。

運(yùn)行本地測(cè)試主方法

執(zhí)行本地測(cè)試主方法，并觀察控制臺(tái)輸出結(jié)果，確保算法按照預(yù)期工作。

算法復(fù)雜度分析

整個(gè)算法只需遍歷一遍字符串s，因此時(shí)間復(fù)雜度為O(n)，其中n是括號(hào)字符串的長度。同時(shí)需要?jiǎng)?chuàng)建一個(gè)長度為n的數(shù)組dp，所以空間復(fù)雜度也是O(n)。