資訊專欄INFORMATION COLUMN
摘要：一個(gè)合法的字符串是指左括號(hào)和右括號(hào)必定成對(duì)出現(xiàn)。要求得出用最少次數(shù)的刪除可以得到的所有的合法字符串。最后兩個(gè)結(jié)果重復(fù)，因此只保留，兩個(gè)結(jié)果。最終生成的合法字符串為。方法相同于上一種情況。其中出現(xiàn)了兩次。在該下標(biāo)前的刪除將會(huì)產(chǎn)生重復(fù)的結(jié)果。
題目要求
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
現(xiàn)在有一個(gè)字符串包含一些左右括號(hào)以及字母。一個(gè)合法的字符串是指左括號(hào)和右括號(hào)必定成對(duì)出現(xiàn)。要求得出用最少次數(shù)的刪除可以得到的所有的合法字符串。
思路和代碼這道題目的思路源自于評(píng)論區(qū)。剛開始會(huì)有點(diǎn)難以理解，現(xiàn)在試圖理清這個(gè)思路。
先從題目中給的例子入手：()())()
當(dāng)遍歷到第五個(gè)括號(hào)時(shí)，我們發(fā)現(xiàn)這個(gè)括號(hào)的存在非法。因此我們會(huì)從當(dāng)前的三個(gè)右括號(hào)（下標(biāo)分別為1, 3, 4）中選擇一個(gè)刪去。那么選擇哪個(gè)呢？其實(shí)選擇任意一個(gè)右括號(hào)都可以使當(dāng)前的的子字符串合法，并依次生成如下三個(gè)結(jié)果(())，()()，()()。最后兩個(gè)結(jié)果重復(fù)，因此只保留(())，()()兩個(gè)結(jié)果。最終生成的合法字符串為[()()(), (())()]。
這里說明了一種情況，即右括號(hào)的數(shù)量多于左括號(hào)的數(shù)量。那么如何處理左括號(hào)的數(shù)量多于右括號(hào)數(shù)量的場(chǎng)景呢？如()(()
其實(shí)，我們只需要將其倒置為)(()(，并且將)(視為一組合法的括號(hào)即可。這時(shí)我們會(huì)看見下標(biāo)2上的左括號(hào)不合法，對(duì)之進(jìn)行處理即可。方法相同于上一種情況。
還要考慮一個(gè)問題，即出現(xiàn)重復(fù)的結(jié)果集的問題，就像例子中重復(fù)生成的的()()。我們?nèi)绾尾拍鼙苊馐褂肧et來過濾掉重復(fù)的結(jié)果呢？
還是舉一個(gè)例子：()())())
按照之前的處理，當(dāng)我們遍歷到下標(biāo)4上的右括號(hào)時(shí)，我們有三個(gè)刪除選擇。而且我們發(fā)現(xiàn)當(dāng)出現(xiàn)連續(xù)的右括號(hào)時(shí)，刪除該連續(xù)括號(hào)中的任意一個(gè)產(chǎn)生的結(jié)果都相同。所以默認(rèn)情況下，我們刪除第一個(gè)括號(hào)。這時(shí)處理后的字符串為()()())以及(())())。
再對(duì)()()())處理，同樣的，當(dāng)我們遇到最后一個(gè)右括號(hào)時(shí)，只需要?jiǎng)h除任意一個(gè)右括號(hào)就可以使數(shù)組成為合法數(shù)組，那么我們先根據(jù)第一個(gè)原則，刪除連續(xù)右括號(hào)的第一個(gè)括號(hào)，可以產(chǎn)生沒有重復(fù)的結(jié)果為(()()),()(())，()()()。
同理(())())可以處理出結(jié)果(()())，(())()。其中(()())出現(xiàn)了兩次。我們?nèi)绾伪苊膺@樣的重復(fù)呢？這時(shí)我們需要記錄一下最后一次刪除所在的下標(biāo)。在該下標(biāo)前的刪除將會(huì)產(chǎn)生重復(fù)的結(jié)果。這里我們看到最后一次刪除的下標(biāo)為3。對(duì)下標(biāo)3之前的刪除將會(huì)帶來重復(fù)的結(jié)果(()())
