题目

类型：BFS
image.png

解题思路

使用回溯算法，尝试遍历所有可能的去掉非法括号的方案。

首先利用括号匹配的规则求出该字符串 s 中最少需要去掉的左括号的数目 lremove 和右括号的数目 rremove，然后我们尝试在原字符串 s 中去掉 lremove 个左括号和 rremove 个右括号，然后检测剩余的字符串是否合法匹配，如果合法匹配则则认为该字符串为可能的结果，利用回溯算法来尝试搜索所有可能的去除括号的方案。

在进行回溯时可以利用以下的剪枝技巧来增加搜索的效率：

  • 充分利用括号左右匹配的特点（性质），因此设置变量 lcount 和 rcount，分别表示在遍历的过程中已经用到的左括号的个数和右括号的个数，当出现 lcount<rcount 时，则认为当前的字符串已经非法，停止本次搜索。
  • 从字符串中每去掉一个括号，则更新 lremove 或者 rremove，当发现剩余未尝试的字符串的长度小于 lremove+rremove 时，则停止本次搜索。
  • 当 lremove 和 rremove 同时为 0 时，则检测当前的字符串是否合法匹配，如果合法匹配则将其记录下来。

由于记录的字符串可能存在重复，因此需要对重复的结果进行去重，去重的办法有如下两种：

  • 利用哈希表对最终生成的字符串去重。
  • 在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 (((())，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 ((())，因此在尝试搜索时，只需去掉一个左括号进行下一轮搜索，不需要将前四个左括号都尝试一遍。

代码

  1. class Solution {
  2.     private List<String> res = new ArrayList<String>();
  4.     public List<String> removeInvalidParentheses(String s) {
  5.         int lremove = 0;
  6.         int rremove = 0;
  8.         for (int i = 0; i < s.length(); i++) {
  9.             if (s.charAt(i) == '(') {
  10.                 lremove++;
  11.             } else if (s.charAt(i) == ')') {
  12.                 if (lremove == 0) {
  13.                     rremove++;
  14.                 } else {
  15.                     lremove--;
  16.                 }
  17.             }
  18.         }
  19.         helper(s, 0, 0, 0, lremove, rremove);
  21.         return res;
  22.     }
  24.     private void helper(String str, int start, int lcount, int rcount, int lremove, int rremove) {
  25.         if (lremove == 0 && rremove == 0) {
  26.             if (isValid(str)) {
  27.                 res.add(str);
  28.             }
  29.             return;
  30.         }
  32.         for (int i = start; i < str.length(); i++) {
  33.             if (i != start && str.charAt(i) == str.charAt(i - 1)) {
  34.                 continue;
  35.             }
  36.             // 如果剩余的字符无法满足去掉的数量要求，直接返回
  37.             if (lremove + rremove > str.length() - i) {
  38.                 return;
  39.             }
  40.             // 尝试去掉一个左括号
  41.             if (lremove > 0 && str.charAt(i) == '(') {
  42.                 helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove - 1, rremove);
  43.             }
  44.             // 尝试去掉一个右括号
  45.             if (rremove > 0 && str.charAt(i) == ')') {
  46.                 helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove, rremove - 1);
  47.             }
  48.             if (str.charAt(i) == ')') {
  49.                 lcount++;
  50.             } else if (str.charAt(i) == ')') {
  51.                 rcount++;
  52.             }
  53.             // 当前右括号的数量大于左括号的数量则为非法,直接返回.
  54.             if (rcount > lcount) {
  55.                 break;
  56.             }
  57.         }
  58.     }
  60.     private boolean isValid(String str) {
  61.         int cnt = 0;
  62.         for (int i = 0; i < str.length(); i++) {
  63.             if (str.charAt(i) == '(') {
  64.                 cnt++;
  65.             } else if (str.charAt(i) == ')') {
  66.                 cnt--;
  67.                 if (cnt < 0) {
  68.                     return false;
  69.                 }
  70.             }
  71.         }
  73.         return cnt == 0;
  74.     }
  75. }