Answers for "Remove Invalid Parenthesis Faster and Easier"

C#
0

Remove Invalid Parenthesis Faster and Easier

public List<String> removeInvalidParentheses(String s) {
    Set<String> res = new HashSet<>();
    int rmL = 0, rmR = 0;
    for(int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == '(') rmL++;
        if(s.charAt(i) == ')') {
            if(rmL != 0) rmL--;
            else rmR++;
        }
    }
    DFS(res, s, 0, rmL, rmR, 0, new StringBuilder());
    return new ArrayList<String>(res);  
}

public void DFS(Set<String> res, String s, int i, int rmL, int rmR, int open, StringBuilder sb) {
    if(i == s.length() && rmL == 0 && rmR == 0 && open == 0) {
        res.add(sb.toString());
        return;
    }
    if(i == s.length() || rmL < 0 || rmR < 0 || open < 0) return;

    char c = s.charAt(i);
    int len = sb.length();

    if(c == '(') {
        DFS(res, s, i + 1, rmL - 1, rmR, open, sb);
        DFS(res, s, i + 1, rmL, rmR, open + 1, sb.append(c)); 

    } else if(c == ')') {
        DFS(res, s, i + 1, rmL, rmR - 1, open, sb);
        DFS(res, s, i + 1, rmL, rmR, open - 1, sb.append(c));

    } else {
        DFS(res, s, i + 1, rmL, rmR, open, sb.append(c)); 
    }

    sb.setLength(len);
}
Posted by: Guest on April-29-2021

C# Answers by Framework

Browse Popular Code Answers by Language