三刷 07/2022
Version #2 DFS - optimized without hashset
在()))这种情况，去掉第1,3 1,2 2,3 个)是相同的，所以当一个character等于前面的character的时候，只有当前面的character都remove的情况下再remove当前的character
Time O(2^N)
Space O(N)
Runtime: 11 ms, faster than 75.38% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 43 MB, less than 72.84% of Java online submissions for Remove Invalid Parentheses.
class Solution {
public List<String> removeInvalidParentheses(String s) {
int leftCnt = 0, rightCnt = 0;
int removeCnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != '(' && c != ')') {
continue;
}
if (c == '(') {
leftCnt++;
} else {
rightCnt++;
}
if (rightCnt > leftCnt) {
removeCnt = Math.max(removeCnt, rightCnt - leftCnt);
}
}
rightCnt -= removeCnt;
// System.out.printf("rightCnt=%d\n", rightCnt);
List<String> result = new ArrayList<>();
helper(s, 0, rightCnt, rightCnt, new StringBuilder(), result);
return result;
}
private void helper(String s, int index, int leftCnt, int rightCnt, StringBuilder sb, List<String> result) {
if (index == s.length()) {
if (leftCnt == 0 && rightCnt == 0) {
result.add(sb.toString());
}
return;
}
char c = s.charAt(index);
if (c != '(' && c != ')') {
sb.append(c);
helper(s, index + 1, leftCnt, rightCnt, sb, result);
sb.deleteCharAt(sb.length() - 1);
return;
}
sb.append(c);
if (c == '(') {
helper(s, index + 1, leftCnt - 1, rightCnt, sb, result);
} else if (leftCnt < rightCnt) {
helper(s, index + 1, leftCnt, rightCnt - 1, sb, result);
}
sb.deleteCharAt(sb.length() - 1);
if (index - 1 >= 0 && s.charAt(index - 1) == c && sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
return;
}
// not append
helper(s, index + 1, leftCnt, rightCnt, sb, result);
}
}
Version #1 DFS - with hashset
先计算出remove minimum之后还剩多少个parenthesis，然后recursively enumerate
用hashset去重
Time O(2^N)
Space O(N)
Runtime: 307 ms, faster than 17.92% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 43.1 MB, less than 67.54% of Java online submissions for Remove Invalid Parentheses.
class Solution {
public List<String> removeInvalidParentheses(String s) {
int leftCnt = 0, rightCnt = 0;
int removeCnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != '(' && c != ')') {
continue;
}
if (c == '(') {
leftCnt++;
} else {
rightCnt++;
}
if (rightCnt > leftCnt) {
removeCnt = Math.max(removeCnt, rightCnt - leftCnt);
}
}
rightCnt -= removeCnt;
// System.out.printf("rightCnt=%d\n", rightCnt);
Set<String> result = new HashSet<>();
helper(s, 0, rightCnt, rightCnt, new StringBuilder(), result);
return new ArrayList<>(result);
}
private void helper(String s, int index, int leftCnt, int rightCnt, StringBuilder sb, Set<String> result) {
if (index == s.length()) {
if (leftCnt == 0 && rightCnt == 0) {
result.add(sb.toString());
}
return;
}
char c = s.charAt(index);
if (c != '(' && c != ')') {
sb.append(c);
helper(s, index + 1, leftCnt, rightCnt, sb, result);
sb.deleteCharAt(sb.length() - 1);
return;
}
// not append
helper(s, index + 1, leftCnt, rightCnt, sb, result);
sb.append(c);
if (c == '(') {
helper(s, index + 1, leftCnt - 1, rightCnt, sb, result);
} else if (leftCnt < rightCnt) {
helper(s, index + 1, leftCnt, rightCnt - 1, sb, result);
}
sb.deleteCharAt(sb.length() - 1);
}
}
2ND TRY
Iterate through s to find the minimum number of '(' and ')' that need to be removed
Trying to remove exact number of '(' and ')' by dfs
open is used to check if current state is valid or not
valid means at every time left >= right and in the end left == right
if we removed more that min left/right that need to be removed, also return
It is possible that multiple remove strategy can lead to the same result string
That's why we need a Set<String> to remove duplicate result
71.65 %
class Solution {
public List<String> removeInvalidParentheses(String s) {
Set<String> result = new HashSet<>();
if (s == null) {
return new ArrayList<>();
}
int rmLeft = 0;
int rmRight = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
rmLeft++;
} else if (s.charAt(i) == ')') {
if (rmLeft > 0) {
rmLeft--;
} else {
rmRight++;
}
}
}
dfs(s, 0, rmLeft, rmRight, 0, new StringBuilder(), result);
return new ArrayList<>(result);
}
private void dfs(String s, int index, int rmLeft, int rmRight, int open, StringBuilder sb, Set<String> result) {
// valid if left >= right all the time
if (rmLeft < 0 || rmRight < 0 || open < 0) {
return;
}
if (index == s.length()) {
if (rmLeft == 0 && rmRight == 0) {
result.add(sb.toString());
}
return;
}
char curr = s.charAt(index);
int len = sb.length();
if (curr == '(') {
// not add -> remove 1 left
dfs(s, index + 1, rmLeft - 1, rmRight, open, sb, result);
// add current left
dfs(s, index + 1, rmLeft, rmRight, open + 1, sb.append(curr), result);
} else if (curr == ')') {
// not add -> remove 1 right
dfs(s, index + 1, rmLeft, rmRight - 1, open, sb, result);
// add current right, close 1 open
dfs(s, index + 1, rmLeft, rmRight, open - 1, sb.append(curr), result);
} else {
dfs(s, index + 1, rmLeft, rmRight, open, sb.append(curr), result);
}
sb.setLength(len);
}
}
1ST TRY
如何求要去掉的 '(' 和 ')' 的个数
确定以上之后
在任意时刻 #left >= #right 终止时刻 #left == #right
int open = left - right
if (open < 0) immediately return, no need to go deep
66.33 %
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
if (s == null) return result;
Set<String> visited = new HashSet<>();
int rmvLeft = 0, rmvRight = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
rmvLeft++;
} else if (c == ')') {
if (rmvLeft > 0) {
rmvLeft--;
} else {
rmvRight++;
}
}
}
removeInvalidParenthesesDFSHelper(s, 0, 0, rmvLeft, rmvRight, new StringBuilder(), result, visited);
return result;
}
//open = #left - #right
private void removeInvalidParenthesesDFSHelper(String s, int index, int open, int rmvLeft, int rmvRight, StringBuilder path, List<String> result, Set<String> visited) {
//success
if (index == s.length() && open == 0) {
String res = path.toString();
if (!visited.contains(res)) {
result.add(res);
visited.add(res);
}
return;
}
if (index >= s.length() || rmvLeft < 0 || rmvRight < 0 || open < 0) return;
char curr = s.charAt(index);
int pathLength = path.length();
if (curr == '(') {
//remove current left parenthesis
removeInvalidParenthesesDFSHelper(s, index + 1, open, rmvLeft - 1, rmvRight, path, result, visited);
path.append(curr);
removeInvalidParenthesesDFSHelper(s, index + 1, open + 1, rmvLeft, rmvRight, path, result, visited);
path.setLength(pathLength);
} else if (curr == ')') {
removeInvalidParenthesesDFSHelper(s, index + 1, open, rmvLeft, rmvRight - 1, path, result, visited);
path.append(curr);
removeInvalidParenthesesDFSHelper(s, index + 1, open - 1, rmvLeft, rmvRight, path, result, visited);
path.setLength(pathLength);
} else {
path.append(curr);
removeInvalidParenthesesDFSHelper(s, index + 1, open, rmvLeft, rmvRight, path, result, visited);
path.setLength(pathLength);
}
}
}
Version #2 BFS
42.74 %
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
很自然的想到BFS的最短路径问题
每一层分别在原来currString的基础上移除掉任意一个parentheses加入到queue中
每次Poll出currString之后，判断是否valid，如果已经发现有valid存在，证明已经找到了最短的路径，就设置一个flag，不再将下一层放进queue里面
此处有一个有一点点tricky的地方，如果现在的currString不是该层的第一个node，那么之前已经加入了一些下一层的node，如果这些node也是valid？会不会被加入queue呢？答案是不会的，因为括号是成对出现的，如果当前层存在valid的情况，那么要再继续移除两个括号以后才会有下一个valid的层，所以不需要对下一层的答案进行特殊的譬如length < minLength之类的判断，因为它们一定不是valid的的
不过，如果走到length < minLength以后可以直接return(加完之后反而慢了。。。。无语)
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
if (s == null) return result;
removeInvalidParenthesesBFSHelper(s, result);
return result;
}
private void removeInvalidParenthesesBFSHelper(String s, List<String> result) {
Queue<String> que = new LinkedList<>();
Set<String> visited = new HashSet<>();
que.offer(s);
visited.add(s);
String currStr;
boolean found = false;
int levelSize = 0;
while (!que.isEmpty()) {
currStr = que.poll();
//System.out.println(currStr);
if(isValid(currStr)) {
result.add(currStr);
found = true;
}
if (found) continue;
String newString;
//Delete the char at index i
for (int i = 0; i < currStr.length(); i++) {
if (currStr.charAt(i) != '(' && currStr.charAt(i) != ')') continue;
newString = currStr.substring(0, i) + currStr.substring(i + 1);
if (!visited.contains(newString)) {
que.offer(newString);
visited.add(newString);
}
}
}
}
private boolean isValid(String str) {
int count = 0;
for (int i = 0; i < str.length(); i++) {
char character = str.charAt(i);
if (character == '(') count++;
if (character == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
}
No comments:
Post a Comment