https://leetcode.com/problems/generate-parentheses/ 描述 Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses. 給定n對括號，要求返回所有這些括號組成的不同的合法的字符串 For example, given n = 3, a solution set is: 輸入：n = 3 "((()))" ,"(()())" ,"(())()" ,"()(())" ,"()()()"
題解 這道題目非常有意思，解法也很多，還是老規(guī)矩，我們先由易到難，先從最簡單的方法開始入手。 我們來簡單分析一下題目，n個括號對意味著字符串的長度是2n，我們利用排列組合可以計算出，所有的組合種數(shù)一共有 算一下會知道，這個數(shù)是很大的，也就是說我們哪怕一開始就知道答案，把答案遍歷一遍也會有很高的耗時，所以這道題對于時間復(fù)雜度的要求應(yīng)該不會很高。 暴力 能想到最簡單的方法，當(dāng)然是暴力，不要看不起這個樸素的算法，很多時候靈感都是從暴力當(dāng)中獲取的。 但是這道題暴力不太容易寫，因為會有一種無從入手的感覺，我們知道要暴力，但是并不知道應(yīng)該怎樣暴力。 這道題不存在可以直接枚舉的樸素元素，必須要我們拐個彎才行。 怎么拐彎呢，其實答案我剛才已經(jīng)說出來了。 n個括號對，也就是說一共2n個字符，我們可以枚舉n個'('分別放在什么位置，剩下的自然就是')'了。 看起來很有道理，但是有一個問題，就是這個思路并沒有辦法通過循環(huán)直接實現(xiàn)。 這其實已經(jīng)進(jìn)化成了一個搜索問題 了，我們要搜索所有可以擺放括號的可能性。 如果你能從暴力方法跳躍到搜索問題，那么說明你離寫出代碼已經(jīng)很接近了。 如果不行，那么我建議你花點(diǎn)時間去學(xué)習(xí)一下搜索算法專題。 對于搜索問題而言，這已經(jīng)很簡單了，我們搜索的空間是明確的，2n個位置，搜索的內(nèi)容，對于每個位置我們可以擺放'('也可以擺放')'。 那么代碼自然而然呼之欲出： def dfs(pos, left , right , n, ret , cur_str):"" " po s: ?當(dāng)前枚舉的位置t: ?已經(jīng)放置的左括號的數(shù)量t: ?已經(jīng)放置的右括號的數(shù)量t: ?放置答案的數(shù)組"" " if ?pos == 2 *n:ret .append (cur_str)return if ?left ?< n:1 , left +1 , right , n, ret , cur_str+'(' )if ?right ?< n:1 , left , right +1 , n, ret , cur_str+')' )
這個程序遍歷運(yùn)行之后還沒有結(jié)束，我們還需要判斷生成出來的括號是否合法 ，也就是說括號需要匹配上。 我們可以用一個棧來判斷括號是否能夠匹配，比如我們遇見左括號就進(jìn)棧，遇見右括號則判斷棧頂，如果棧頂是左括號，那么棧頂?shù)淖罄ㄌ柍鰲＃駝t則入棧，最后判斷棧是否為空。 這個算法實現(xiàn)當(dāng)然不難，但是如果你仔細(xì)去想了，你會發(fā)現(xiàn)完全沒有必要用棧，因為如果我們遇到右括號的時候，棧頂不為左括號，那么一定最后是無法匹配的。 因為后面出現(xiàn)的左括號不能匹配前面出現(xiàn)的右括號，正所謂往者不可追 就是這個道理。 【狗頭】 優(yōu)化 我們來思考一個問題： 什么情況會出現(xiàn)右括號遇不到左括號呢？ 只有一種情況，就是當(dāng)前出現(xiàn)右括號的個數(shù)超過了左括號，也就是說我們遍歷一下字符串，如果中途出現(xiàn)右括號數(shù)量超過左括號的情況，那么就說明這個字符串是非法的。 看起來沒毛病對吧，但是有問題，我們為什么不在枚舉的時候就判斷呢 ，如果左括號放入的數(shù)量已經(jīng)等于右括號了，那么就不往里放置右括號，這樣不就可以保證搜索到的一定是合法的字符串嗎？ 如果你能想到這一層，說明你對搜索的理解已經(jīng)很不錯了。 我們看一下改動之后的代碼： def dfs(pos, left , right , n, ret , cur_str):"" " po s: ?當(dāng)前枚舉的位置t: ?已經(jīng)放置的左括號的數(shù)量t: ?已經(jīng)放置的右括號的數(shù)量t: ?放置答案的數(shù)組"" " if ?pos == 2 *n:ret .append (cur_str)return if ?left ?< n:1 , left +1 , right , n, ret , cur_str+'(' )if ?right ?< n and ?right ?< left: 1 , left , right +1 , n, ret , cur_str+')' )
大部分代碼都沒有變化，只是在right < n后面加入了一個right < left這個條件。 看似只有一個條件，但是這個條件起到的作用至關(guān)重要。 整個算法的效率有了質(zhì)的提升，實際上這也是效率最高的算法。 構(gòu)造 上面的方案在LeetCode官方當(dāng)中都有收入，也是比較常規(guī)的解法，下面要介紹的方法是我的原創(chuàng)，我個人感覺也比較有意思，分享給大家。 在之前的文章當(dāng)中我們介紹過分治法，分治法的核心是將一個看似無法求解的大問題，分解成比較容易解決的小問題，最后加以解決。 這道題當(dāng)中，我們直接求n時的解法是比較困難的，沒辦法直接獲得，我們能不能也試著使用分治的方法來解決呢？ 我們來觀察一下數(shù)據(jù)，當(dāng)n=1的時候，很簡單，結(jié)果是()，只有這一種。 當(dāng)n=2呢？ 有兩種，分別是(())和()()，當(dāng)n=3呢？ 有5種： ((())), ()(()), ()()(), (()()), (())()。 這當(dāng)中有沒有規(guī)律呢？ 我們用solution(n)表示n對應(yīng)的解法，那么我們可以寫出solution(n)對應(yīng)的公式： 上面這個式子有點(diǎn)像是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程，雖然不完全一樣，但是大概是那么回事。 也就是說我們可以用比答案規(guī)模小的答案組裝成現(xiàn)在的答案 。 比如n=3時的答案，等于n=2時的答案和n=1時答案的拼接。 比如: solution(1) + solution(2) 可以得到： ()()()和()(())，solution(2) + solution(1)可以得到 ()()()和(())()。 但是還有一種答案無法通過拼接得到就是( solution(2) )。 也就是說在solution(2)的答案外面包一層括號。 那為什么不用考慮solution(1)的答案外面包兩層括號呢？ 答案很簡單，因為solution(2)已經(jīng)包括了這樣的情況，所以我們只用往下考慮一層。 不過還沒有結(jié)束，還有一點(diǎn)小問題，就是這樣得到的答案可能會有重復(fù) ，所以我們需要去重，利用set我們可以很簡單做到這點(diǎn)，讓我們一起來看代碼：
class ?Solution :def ?generateParenthesis (self, n: int) ?-> List[str]:# 記錄下n=0和1時的答案 0 ] = set(["" ])1 ] = set(["()" ])# 遍歷小于n的所有長度 for ?i in ?range(2 , n+1 ):# 遍歷小于n的所有長度 for ?j in ?range(1 , i):# 構(gòu)造答案 for ?s in ?ans1:for ?t in ?ans2:# 構(gòu)造 ( solution(n-1) )這種答案 for ?s in ?solutionMap[i-1 ]:"(" ?+ s + ")" )return ?list(solutionMap[n])
在C++當(dāng)中，這兩種方法的效率差不多，但是使用Python的話，構(gòu)造的方法要更快一些。 和搜索這種方法相比，搜索是不知道答案去搜尋答案，而構(gòu)造法是知道答案大概長什么樣子，依據(jù)一定的規(guī)則生產(chǎn)答案 。 可以說是兩種不同思路的解法，也是我本人很喜歡這道題的原因。 這道題的代碼都不長，但是思路挺有意思，希望大家會喜歡。 今天的文章就是這些，如果覺得有所收獲，請順手點(diǎn)個在看或者轉(zhuǎn)發(fā) 吧，你們的舉手之勞對我來說很重要。 