/**
Given a string s that contains parentheses and letters, remove the minimum
number of invalid parentheses to make the input string valid.
Return all the possible results. You may return the answer in any order.
Example 1:
Input: s = "()())()"
Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'.
There will be at most 20 parentheses in s.
Related Topics广度优先搜索 | 字符串 | 回溯
👍 778, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<String> removeInvalidParentheses(String s) {
Set<String> visitedSet = new HashSet<>();
List<String> result = new ArrayList<>();
int maxLen = 0;
Queue<String> candQueue = new LinkedList<>();
visitedSet.add(s);
candQueue.add(s);
while (!candQueue.isEmpty()) {
String cand = candQueue.poll();
if (isValid(cand)) {
result.add(cand);
if (cand.length() > maxLen) {
maxLen = cand.length();
}
continue;
}
if (cand.length() <= maxLen) {
continue;
}
for (int i = 0; i < cand.length(); i++) {
String sub;
if (i == 0) {
sub = cand.substring(1);
} else if (i == cand.length() - 1) {
sub = cand.substring(0, cand.length() - 1);
} else {
sub = cand.substring(0, i) + cand.substring(i + 1);
}
if (visitedSet.contains(sub)) {
continue;
}
candQueue.add(sub);
visitedSet.add(sub);
}
}
final int ff = maxLen;
return result.stream().filter(p->p.length() == ff).collect(Collectors.toList());
}
private boolean isValid(String s) {
int cnt = 0;
for (char ch : s.toCharArray()) {
if (ch == '(') {
cnt++;
} else if (ch == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
//leetcode submit region end(Prohibit modification and deletion)
