301. Remove Invalid Parentheses
use unmatched count to find the final ans
if unmatched count == 0 means can be add to result (and i == s.size()...currStr == maxLen
### ๅป้ๆนๆณ
็ฌฌไธๅๅญๆฏ B (ret.back()), ไนๅพ่ฆๅ ็ ๏ผกๆฏ็ธๅ็ๅญ็ฌฆ(S[i), ไธญ้ * ๆฏๅ
ถไปๅญ
ๅฆๆ่ฆๅจถๅ
ฉๅ๏ผก, ๆ้บผๅๆๆฏ unique็
A * A * A * A s[i]
B ret
B โ A (ret.back() โ S[0]) โ ๅฏไปฅ ไธ้ธ A (x), ไนๅฏ้ธ A , ่ท 2^n ๆณๆณไธๆจฃ
```java
if ret.back() != s[i]
ret + s[i] // ้ธ A (s[i]), ret.back() ๆฏB
ret // ไธ้ธ A
```
ๅฆๆ
B = A โ ไธ
```java
if ret.back() == s[i]
ret + s[i] // ไธๅฎๅช่ฝ้ธ A
```
ๆไปฅๅชๆ
```java
// ๅ
ถไป้ฝ่ฆ
ret + s[i] // ้ธ A
if ret.back() != s[i]
ret // ไธ้ธ A
```T: O(2^n) in worst
S: O(n), stack depth
class Solution {
int maxLen;
public List<String> removeInvalidParentheses(String s) {
// first use greedy, like leetcode 921 idea, to find result maxLen
int count = 0;
int remove = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
count++;
} else if (c == ')') { // notice this...
count--;
}
if (count < 0) {
count = 0;
remove++;
}
}
remove += count;
maxLen = s.length() - remove;
List<String> res = new ArrayList<>();
dfs(res, s, 0, "", 0);
return res;
}
// i: curr index
// curStr: current String result
// count: unmatched count
/*
use dfs remove duplicate strategy to do dfs
*/
private void dfs(List<String> res, String s, int i, String curStr, int count) {
// check left: count+, right: count -, so count < 0 means right > left, not valid
// maxlen is the final Len we caculated before
if (count < 0 || curStr.length() > maxLen) {
return;
}
// this two if expression can't combine, index will wrong
if (i == s.length()) { // i go to the string end
if (count == 0 && curStr.length() == maxLen) {
res.add(curStr);
}
return;
}
// no bucket, no more for
// add one more next char
String newStr = curStr + s.charAt(i);
// not '(', ')' , go to next dfs(i+1, newStr, count not change
if (s.charAt(i) != '(' && s.charAt(i) != ')') {
dfs(res, s, i+1, newStr, count);
} else { // '(', ')' case
// remove duplicate thinking:
// case 1: curr string last char != add new char
// case 2: curr string last char == add new char
// do this, pick next char
// check one more '(', ')' case, go to next dfs(i+1, newStr, count+1 or count-1
dfs(res, s, i+1, newStr, count+(s.charAt(i)=='('?1:-1));
// remove duplicate thinking:
// curr string last char != add new char
// don't pick next char
// go to next dfs(i+1, newStr, count not change
if (curStr.length() == 0 || curStr.charAt(curStr.length()-1) != s.charAt(i)) {
dfs(res, s, i+1, curStr, count);
}
}
}
}
/*
T: O(2^n) in worst
S: O(n), stack depth
*/BFS
T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1).
T: O(n*2^(n-1))
S: O(n)
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if (s == null) {
return res;
}
Queue<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offer(s);
visited.add(s);
boolean foundMinRemove = false;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curr = queue.poll();
// find min length string, so set foundMinRemove true
if (isValid(curr)) {
res.add(curr);
foundMinRemove = true;
}
// don't need to try to remove more char
if (foundMinRemove) {
continue;
}
// gen all pattern, remove one char in origin str to try
for (int j = 0; j < curr.length(); j++) {
if (curr.charAt(j) != '(' && curr.charAt(j) != ')') {
continue;
}
String newStr = curr.substring(0, j) + curr.substring(j+1);
if (visited.contains(newStr)) {
continue;
}
queue.offer(newStr);
visited.add(newStr);
}
}
}
return res;
}
private boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
count++;
} else if (c == ')') {
count--;
}
if (count < 0) {
return false;
}
}
return count == 0;
}
11/30
/*
Return all the possible results.
so what we can do is brutely using dfs or bfs to remove parentheses
at last, find all the valid results
1. calculate the result maxlen
int count = 0;
int remove = 0;
if (curr == '(')
count++
else if (curr == ')') {
count--;
if (count < 0) {
count = 0;
remove++;
}
}
remove += count;
int maxLen = str.length() - remove;
this can be the validation rule for dfs
2. dfs, how to avoid duplicate, use set to remove duplicate is a way
smarter way is like followings:
(((( ))
2^4 = 16
c(4,2) = 2x3x4/2x2 = 6
ooxx => what we want
oxox
oxxo
xoxo
xxoo
xoox
A new add next char
B cur str's last char
X -> abandon
O -> append
rule:
if (B != A) {
B dont append anything
or
B.append(A)
}
if (B == A) {
B.append(A)
}
A * A * A * A
B X X. X. X. B
B. X. X. X. A. BA
B. X. X. A. -> if BA, next A must append, because (new add next char is A == cur str's last char is A, A == A
B. X. X. A. A BAA => so if we want choose 2 A from 4A, that's the unique way! no duplicate
B. X. A. A. A BAAA
B. A. A. A. A BAAAA
B. X. X. A. A BAA => so if we want choose 2 A from 4A, that's the unique way! no duplicat
*/class Solution {
int maxLen = 0;
public List<String> removeInvalidParentheses(String s) {
int count = 0;
int remove = 0;
for (char curr : s.toCharArray()) {
if (curr == '(')
count++;
else if (curr == ')') {
count--;
if (count < 0) {
count = 0;
remove++;
}
}
}
remove += count;
maxLen = s.length() - remove;
List<String> res = new ArrayList();
dfs(res, s, 0, "", 0);
return res;
}
private void dfs(List<String> res, String s, int i, String currStr, int count) {
if (count < 0 || currStr.length() > maxLen) {
return;
}
if (i == s.length()) {
if (count == 0 && currStr.length() == maxLen) {
res.add(currStr);
}
return;
}
String next = s.substring(i, i+1);
if (s.charAt(i) != '(' && s.charAt(i) != ')') {
dfs(res, s, i+1, currStr+next, count);
} else {
int calCount = (s.charAt(i) == '(') ? 1 : -1;
dfs(res, s, i+1, currStr+next, count + calCount);
char nextChar = s.charAt(i);
if ("".equals(currStr) || currStr.charAt(currStr.length()-1) != nextChar) {
dfs(res, s, i+1, currStr, count); // dont pick next char
}
}
}
}Last updated
