1+ // 301. 删除无效的括号
2+
3+
4+ /*
5+ 回溯：
6+ 1、题目要求将所有最长合法方案输出，因此不可能有别的优化，只能进行「爆搜」，可以使用 DFS 实现回溯搜索
7+ 2、所有的合法方案，必然有左括号的数量与右括号数量相等。令左括号的得分为 1；右括号的得分为 −1。则合法方案会有如下性质：
8+ 1）对于一个合法的方案而言，必然有最终得分为 0；
9+ 2）搜索过程中不会出现得分值为 负数 的情况，即右括号数量大于左括号数量时为非法
10+ 3、预处理出「爆搜」过程的最大得分：maxScore = min(左括号的数量, 右括号的数量)，即合法左括号先全部出现在左边，之后使用最多的合法右括号进行匹配
11+ 4、枚举过程中出现字符分三种情况：
12+ 1）左括号：如果增加当前 ( 后，仍为合法子串，即 score+1 <= maxscore 时，我们可以选择添加该左括号，也能选择不添加
13+ 2）右括号：如果增加当前 ) 后，仍为合法子串，即 score-1 >= 0 时，我们可以选择添加该右括号，也能选择不添加
14+ 3）普通字符：直接添加
15+ 5、使用 Set 进行方案去重，maxLen 记录「爆搜」过程中的最大子串，然后只保留长度等于 maxLen 的子串
16+ 6、回溯过程的公共变量作为成员变量，方法独有的变量作为局部变量
17+ 7、定义递归函数：
18+ 1）剪枝条件：分数score非法，即左括号或右括号的数量多了
19+ 2）终止条件：遍历完字符串，判断 分数是否为0、子串长度是否大于等于当前最大长度，若大于最大长度则更新最大长度，并清空集合，最后将将子串加入集合
20+ 3）递归回溯：遍历字符，调用递归方法构造并校验子串。由于变量的改变在入参处理，所以递归结束后 下一个递归参数仍然使用原变量处理，多个递归方法参数互不影响，即回溯
21+ 4）入参变化：
22+ ① 一次递归即遍历下一个字符，索引index加1
23+ ② 添加左括号时，分数score加1，子串subs加上该字符。不添加时分数score不变，子串subs不变
24+ ③ 添加右括号时，分数score减1，子串subs加上该字符。不添加时分数score不变，子串subs不变
25+ ④ 字母必须添加，分数score不变，子串subs加上该字符
26+ */
27+ class Solution {
28+ int n , maxScore , maxLen ;
29+ String s ;
30+ Set <String > set = new HashSet <>();
31+ public List <String > removeInvalidParentheses (String s ) {
32+ this .s = s ;
33+ n = s .length ();
34+ int left = 0 , right = 0 ;
35+ for (char c : s .toCharArray ()) {
36+ if (c == '(' ) {
37+ left ++;
38+ } else if (c == ')' ) {
39+ right ++;
40+ }
41+ }
42+ maxScore = Math .min (left , right );
43+ track (0 , 0 , "" );
44+ return new ArrayList <>(set );
45+ }
46+
47+ private void track (int index , int score , String subs ) {
48+ if (score < 0 || score > maxScore ) {
49+ return ;
50+ }
51+ if (index == n ) {
52+ if (score == 0 && subs .length () >= maxLen ) {
53+ if (subs .length () > maxLen ) {
54+ maxLen = subs .length ();
55+ set .clear ();
56+ }
57+ set .add (subs );
58+ }
59+ return ;
60+ }
61+ char c = s .charAt (index );
62+ if (c == '(' ) {
63+ track (index + 1 , score + 1 , subs + String .valueOf (c ));
64+ track (index + 1 , score , subs );
65+ } else if (c == ')' ) {
66+ track (index + 1 , score - 1 , subs + String .valueOf (c ));
67+ track (index + 1 , score , subs );
68+ } else {
69+ track (index + 1 , score , subs + String .valueOf (c ));
70+ }
71+ }
72+ }
73+
74+
75+ /*
76+ 1、上一解法是在搜索过程中去更新最后的 maxLen，但实际上可以通过预处理，得到最后的「应该删除的左括号数量」和「应该删掉的右括号数量」，来直接得到最终的 maxLen，因此可以多增加一层剪枝
77+ 2、遍历字符串时，对左括号数量和右括号数量进行匹配抵消，最终剩下的数量就是应该删除的括号数量，由字符串长度 减去 应该删除的括号数量 得到 最终子串长度
78+ 3、定义递归函数：
79+ 1）剪枝条件：分数score非法，即左括号或右括号的数量多了。应该删除括号数量非法，即删多了
80+ 2）校验合法条件：应该删除括号数量为0、子串长度等于最大长度，则将子串加入集合
81+ 3）终止条件：遍历完字符串，索引等于字符串长度
82+ 4）递归回溯：遍历字符，调用递归方法构造并校验子串。由于变量的改变在入参处理，所以递归结束后 下一个递归参数仍然使用原变量处理，多个递归方法参数互不影响，即回溯
83+ 5）入参变化：
84+ ① 一次递归即遍历下一个字符，索引index加1
85+ ② 添加左括号时，分数score加1，子串subs加上该字符。不添加时分数score不变，子串subs不变
86+ ③ 添加右括号时，分数score减1，子串subs加上该字符。不添加时分数score不变，子串subs不变
87+ ④ 字母必须添加，分数score不变，子串subs加上该字符
88+ ⑤ 不添加左括号时，应该删除左括号数量leftDel减1。添加时则不变
89+ ⑥ 不添加右括号时，应该删除右括号数量rightDel减1。添加时则不变
90+ */
91+ class Solution {
92+ int n , maxScore , maxLen ;
93+ String s ;
94+ Set <String > set = new HashSet <>();
95+ public List <String > removeInvalidParentheses (String s ) {
96+ this .s = s ;
97+ n = s .length ();
98+ int left = 0 , right = 0 ;
99+ int leftDel = 0 , rightDel = 0 ;
100+ for (char c : s .toCharArray ()) {
101+ if (c == '(' ) {
102+ left ++;
103+ leftDel ++;
104+ } else if (c == ')' ) {
105+ right ++;
106+ if (leftDel != 0 ) {
107+ leftDel --;
108+ } else {
109+ rightDel ++;
110+ }
111+ }
112+ }
113+ maxScore = Math .min (left , right );
114+ maxLen = n - leftDel - rightDel ;
115+ track (0 , 0 , leftDel , rightDel , "" );
116+ return new ArrayList <>(set );
117+ }
118+
119+ private void track (int index , int score , int leftDel , int rightDel , String subs ) {
120+ if (leftDel < 0 || rightDel < 0 || score < 0 || score > maxScore ) {
121+ return ;
122+ }
123+ if (leftDel == 0 && rightDel == 0 && subs .length () == maxLen ) {
124+ set .add (subs );
125+ }
126+ if (index == n ) {
127+ return ;
128+ }
129+ char c = s .charAt (index );
130+ if (c == '(' ) {
131+ track (index + 1 , score + 1 , leftDel , rightDel , subs + String .valueOf (c ));
132+ track (index + 1 , score , leftDel - 1 , rightDel , subs );
133+ } else if (c == ')' ) {
134+ track (index + 1 , score - 1 , leftDel , rightDel , subs + String .valueOf (c ));
135+ track (index + 1 , score , leftDel , rightDel - 1 , subs );
136+ } else {
137+ track (index + 1 , score , leftDel , rightDel , subs + String .valueOf (c ));
138+ }
139+ }
140+ }
0 commit comments