Задача.
Дана строка состоящая из круглых скобок '(' и ')', а также английских букв в нижнем регистре. Нужно удалить минимальное число скобок, чтобы сделать скобочное выражение правильным.
Ссылка на leetcode: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
Примеры:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Input: s = "a)b(c)d"
Output: "ab(c)d"
Input: s = "))(("
Output: ""
Решение.
Можно воспользоваться решением похожей задачи: проверить правильность скобочного выражения.
В основе этого решения лежит использование стека. Мы циклом проходим по строке. Если это открывающаяся скобка - помещаем ее в стек. Если закрывающаяся, то делаем проверку того, что лежит в голове стека. Если это соответствующая открывающаяся скобка, то все в порядке, достаем ее из стека. Если стек пуст или там не соответствующая открывающаяся скобка, то выражение не валидно и скобка не скомпенсирована. Когда закончим цикл по строке, проверим стек пуст или нет. Если нет, это значит, что есть нескомпенсированные скобки, а следовательно скобочное выражение не валидно.
В нашем случае у нас только один вид скобок, поэтому этот код упрощается до:
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
Это решение можно расширить, чтобы получить решение исходной задачи. В тот момент, когда мы встречаем нескомпенсированную скобку, мы можем запоминать ее индекс, чтобы позже ее удалить. Для этого в стеке будем хранить не саму скобку, а ее индекс. Более того будем хранить список всех скобок для удаления в HashSet. В конце, если стек не пуст - то он будет содержать индексы нескомпенсированных скобок, которые нужно удалить. Их мы переместим в наш HashSet. Далее мы снова циклом пройдем по нашей строке, и на ее основе будем создавать новую строку, которая не будет содержать скобок, которые нужно удалить. Это нужно в силу того, что строки в Java immutable. Строку нельзя изменить, можно создать новую.
Итоговый код:
class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
Set<Integer> toRemove = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (stack.isEmpty()) {
toRemove.add(i);
} else {
stack.pop();
}
}
}
while (!stack.isEmpty()) toRemove.add(stack.pop());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!toRemove.contains(i)) sb.append(s.charAt(i));
}
return sb.toString();
}
}
Top comments (0)