原題：https://leetcode.cn/problems/remove-invalid-parentheses/descr...

1 題目

給你一個由若干括號和字母組成的字符串 s ，刪除最小數量的無效括號，使得輸入的字符串有效。

返回所有可能的結果。答案可以按 任意順序 返回。

示例 1：

輸入： s = "()())()"
輸出： ["(())()","()()()"]

示例 2：

輸入： s = "(a)())()"
輸出： ["(a())()","(a)()()"]

示例 3：

輸入： s = ")("
輸出： [""]

提示：

• 1 <= s.length <= 25
• s 由小寫英文字母以及括號 '(' 和 ')' 組成
• s 中至多含 20 個括號

2 分析

從題目提供的信息可以知道：

• 字符串 s 裏除了括號可能還有其他字符
• 我們要刪除無效的括號，但是需要是數量最小的操作

2.1 怎麼找出所有結果

首先第一個想到的辦法就是暴力法，把所有可能的情況都枚舉一遍，那麼每次進入枚舉結果的字符應當符合這個邏輯：

• 如果當前字符為 '('，那麼最終的結果就是：加 / 不加 兩種情況
• 如果當前字符為 '('，那麼最終的結果也是：加 / 不加 兩種情況
• 否則，當前字符只能加到最終的結果裏

2.2 驗證最終結果是否合法

2.2.1 方案一、使用棧來進行判斷

眾所周知，括號可以用棧來進行匹配，只是我們在這個場景下需要處理「非括號」的字符，這裏直接給出代碼：

const isParentheses = (s) => {
  return s === '(' || s === ')'
}

const isValidParentheses = (s, stack = []) => {
  let i = 0
  while (i < s.length) {
    if (!stack.length) {
      stack.push(s[i])
      i++
      continue
    }
    const top = stack[0]
    if (top === '(') {
      if (s[i] === ')') {
        stack.shift()
      } else if (s[i] === '(') {
        stack.push(s[i])
      }
    } else if (top === ')' || s[i] === ')') {
      // 如果最頂部是 )，或者最頂部為非括號並且下一個為 ), 説明不是合法括號
      return false
    } else if (s[i] === '(') {
      stack.shift()
      stack.push(s[i])
    }
    i++
  }
  return stack.every(item => !isParentheses(item)) ? true : !stack.length
}

2.2.2 方案二、使用計數法進行過濾

1. 如果有一個 '(' 就進行執行 left + 1
2. 如果有一個 ')' 就執行 right + 1
3. 如果出現 left - right < 0，那麼説明當前的字符串不合法

其實這個邏輯也很好理解，如果出現了 left - right < 0，那麼就説明當前的字符串是以下這些組合中的其中一種：

• ())
• )

即：要麼是 '(' 數量不夠，要麼就是隻有 ')'

2.3 剪枝 & 去重

2.3.1 剪枝

剪枝很好理解，就是我們在遞歸過程中規避掉已經出現過的值，避免重複計算的手段。
比如在這個場景下，每次遞歸裏當前的字符串就是可以用 map 來進行剪枝的。

2.3.2 去重

在這個場景下，即使進行剪枝了也避免不了最後出現重複的結果，舉個例子：

• )()()) => ()()) => ()()
• )()()) => ()()) => ()()

在這個例子中，當前字符為 ()()) 時就會出現 2 個重複的結果，因此在返回最終結果時還需要做一次去重

3 代碼

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function (s) {
  const dfs = (acc, i, left, right) => {
    let step = s.length - (left + right)
    if (left - right < 0) return
    if (i === s.length) {
      const isValid = left === right && minStep >= step
      if (isValid) {
        minStep = Math.min(minStep, step)
        result.push(acc)
      }
      return
    }
    if (map[acc]) return
    if (s[i] === '(') {
      // 遇到左括號，嘗試加 / 不加
      dfs(acc + s[i], i + 1, left + 1, right)
      dfs(acc, i + 1, left, right)
    }
    else if (s[i] === ')') {
      // 遇到右括號，嘗試加 / 不加
      dfs(acc + s[i], i + 1, left, right + 1)
      dfs(acc, i + 1, left, right)
    }
    // 遇到其他字符，直接保留
    else dfs(acc + s[i], i + 1, left, right)
    map[acc] = true
  }
  
  const result = []
  const map = {}
  let minStep = Infinity
  dfs("", 0, 0, 0)
  return result.length ? [...new Set(result)] : ['']
};

• 時間複雜度：$$O(2^n)$$
• 空間複雜度：$$O(n)$$