資訊專欄INFORMATION COLUMN
摘要：一個合法的字符串是指左括號和右括號必定成對出現。要求得出用最少次數的刪除可以得到的所有的合法字符串。最后兩個結果重復，因此只保留，兩個結果。最終生成的合法字符串為。方法相同于上一種情況。其中出現了兩次。在該下標前的刪除將會產生重復的結果。
題目要求
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())()"]
")(" -> [""]
現在有一個字符串包含一些左右括號以及字母。一個合法的字符串是指左括號和右括號必定成對出現。要求得出用最少次數的刪除可以得到的所有的合法字符串。
思路和代碼這道題目的思路源自于評論區。剛開始會有點難以理解，現在試圖理清這個思路。
先從題目中給的例子入手：()())()
當遍歷到第五個括號時，我們發現這個括號的存在非法。因此我們會從當前的三個右括號（下標分別為1, 3, 4）中選擇一個刪去。那么選擇哪個呢？其實選擇任意一個右括號都可以使當前的的子字符串合法，并依次生成如下三個結果(())，()()，()()。最后兩個結果重復，因此只保留(())，()()兩個結果。最終生成的合法字符串為[()()(), (())()]。
這里說明了一種情況，即右括號的數量多于左括號的數量。那么如何處理左括號的數量多于右括號數量的場景呢？如()(()
其實，我們只需要將其倒置為)(()(，并且將)(視為一組合法的括號即可。這時我們會看見下標2上的左括號不合法，對之進行處理即可。方法相同于上一種情況。
還要考慮一個問題，即出現重復的結果集的問題，就像例子中重復生成的的()()。我們如何才能避免使用Set來過濾掉重復的結果呢？
還是舉一個例子：()())())
按照之前的處理，當我們遍歷到下標4上的右括號時，我們有三個刪除選擇。而且我們發現當出現連續的右括號時，刪除該連續括號中的任意一個產生的結果都相同。所以默認情況下，我們刪除第一個括號。這時處理后的字符串為()()())以及(())())。
再對()()())處理，同樣的，當我們遇到最后一個右括號時，只需要刪除任意一個右括號就可以使數組成為合法數組，那么我們先根據第一個原則，刪除連續右括號的第一個括號，可以產生沒有重復的結果為(()()),()(())，()()()。
同理(())())可以處理出結果(()())，(())()。其中(()())出現了兩次。我們如何避免這樣的重復呢？這時我們需要記錄一下最后一次刪除所在的下標。在該下標前的刪除將會產生重復的結果。這里我們看到最后一次刪除的下標為3。對下標3之前的刪除將會帶來重復的結果(()())
