# 0301. 刪除無效的括號 ## 題目地址(301. 刪除無效的括號) <https://leetcode-cn.com/problems/remove-invalid-parentheses/> ## 題目描述 ``` <pre class="calibre18">``` 刪除最小數量的無效括號，使得輸入的字符串有效，返回所有可能的結果。 說明: 輸入可能包含了除 ( 和 ) 以外的字符。 示例 1: 輸入: "()())()" 輸出: ["()()()", "(())()"] 示例 2: 輸入: "(a)())()" 輸出: ["(a)()()", "(a())()"] 示例 3: 輸入: ")(" 輸出: [""] ``` ``` ## 前置知識 - BFS - 隊列 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 我們的思路是先寫一個函數用來判斷給定字符串是否是有效的。 然后再寫一個函數，這個函數 依次刪除第i個字符，判斷是否有效，有效則添加進最終的返回數組。 這樣的話實現的功能就是， 刪除`一個` 小括號使之有效的所有可能。因此只需要遞歸調用`依次刪除第i個字符`的功能就可以了。 而且由于題目要求是要刪除最少的小括號，因此我們的思路是使用廣度優先遍歷，而不是深度有限的遍歷。  > 沒有動圖，請腦補 ## 關鍵點解析 - 廣度優先遍歷 - 使用隊列簡化操作 - 使用一個visited的mapper， 來避免遍歷同樣的字符串 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=301 lang=javascript * * [301] Remove Invalid Parentheses * * https://leetcode.com/problems/remove-invalid-parentheses/description/ * * algorithms * Hard (38.52%) * Total Accepted: 114.3K * Total Submissions: 295.4K * Testcase Example: '"()())()"' * * 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 * ). * * Example 1: * * * Input: "()())()" * Output: ["()()()", "(())()"] * * * Example 2: * * * Input: "(a)())()" * Output: ["(a)()()", "(a())()"] * * * Example 3: * * * Input: ")(" * Output: [""] * */</span> <span class="hljs-keyword">var</span> isValid = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">let</span> openParenthes = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < s.length; i++) { <span class="hljs-keyword">if</span> (s[i] === <span class="hljs-string">'('</span>) { openParenthes++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (s[i] === <span class="hljs-string">')'</span>) { <span class="hljs-keyword">if</span> (openParenthes === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; openParenthes--; } } <span class="hljs-keyword">return</span> openParenthes === <span class="hljs-params">0</span>; }; <span class="hljs-title">/** * @param {string} s * @return {string[]} */</span> <span class="hljs-keyword">var</span> removeInvalidParentheses = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">if</span> (!s || s.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> [<span class="hljs-string">""</span>]; <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">const</span> queue = [s]; <span class="hljs-keyword">const</span> visited = {}; <span class="hljs-keyword">let</span> current = <span class="hljs-params">null</span>; <span class="hljs-keyword">let</span> removedParentheses = <span class="hljs-params">0</span>; <span class="hljs-title">// 只記錄最小改動</span> <span class="hljs-keyword">while</span> ((current = queue.shift())) { <span class="hljs-keyword">let</span> hit = isValid(current); <span class="hljs-keyword">if</span> (hit) { <span class="hljs-keyword">if</span> (!removedParentheses) { removedParentheses = s.length - current.length } <span class="hljs-keyword">if</span> (s.length - current.length > removedParentheses) <span class="hljs-keyword">return</span> ret.length === <span class="hljs-params">0</span> ? [<span class="hljs-string">""</span>] : ret;; ret.unshift(current); <span class="hljs-keyword">continue</span>; } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < current.length; i++) { <span class="hljs-keyword">if</span> (current[i] !== <span class="hljs-string">')'</span> && current[i] !== <span class="hljs-string">'('</span>) <span class="hljs-keyword">continue</span>; <span class="hljs-keyword">const</span> subString = current.slice(<span class="hljs-params">0</span>, i).concat(current.slice(i + <span class="hljs-params">1</span>)); <span class="hljs-keyword">if</span> (visited[subString]) <span class="hljs-keyword">continue</span>; visited[subString] = <span class="hljs-params">true</span>; queue.push(subString); } } <span class="hljs-keyword">return</span> ret.length === <span class="hljs-params">0</span> ? [<span class="hljs-string">""</span>] : ret; }; ``` ``` ## 擴展 相似問題: [validParentheses](validParentheses.md)