Parenthesis

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == '(') stack.push(')');
        else if (chars[i] == '{') stack.push('}');
        else if (chars[i] == '[') stack.push(']');
        else {
            if (stack.isEmpty() || stack.pop() != chars[i]) return false;
        }
    }
    return stack.isEmpty();
}

def minAddToMakeValid(self, S: str) -> int:
    stack = []
    res = 0
    for c in S:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:
                res += 1
            else:
                stack.pop()
    res += len(stack)
    return res

public String minRemoveToMakeValid(String s) {
    Stack<Integer> stack = new Stack<>();
    Set<Integer> indexToRemove = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') stack.push(i);
        else if (s.charAt(i) == ')') {
            if (stack.isEmpty()) {
                indexToRemove.add(i);
            } else stack.pop();
        }
    }
    while (!stack.isEmpty()) indexToRemove.add(stack.pop());
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (!indexToRemove.contains(i)) sb.append(s.charAt(i));
    }
    return sb.toString();
}

Last updated

Was this helpful?