Задача. Удалить минимальное число скобок, чтобы сделать скобочное выражение правильным. Вернуть все возможное валидные комбинации скобок, с минимальным числом удаленных скобок. Выражение состоит из круглых скобок и букв английского алфавита.
Примеры:
Input: s = "()())()"
Output: ["(())()","()()()"]
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
Input: s = ")("
Output: [""]
Ссылка на leetcode: https://leetcode.com/problems/remove-invalid-parentheses/description/
Решение.
Т.к. нам нужно вернуть все возможные валидные скобочные выражения после удаления минимального числа скобок, то нам нужно организовать некий перебор.
Давайте рассмотрим это на примере: ()())(). Давайте поочередно удалять сначала первую скобку, потом вторую, потом третью и т.д. Получим набор из 7 выражений:
)())(), (())(), ()))(), ()()(), ()()(), ()())), ()())(.
Это все возможные скобочные выражения, полученные из исходного, путем удаления одной скобки.
Для каждого из полученных выражений можно проделать тот же трюк. Например, для первого из них: )())(). Удалим сначала первую скобку, потом вторую и т.д.
Получим еще 6 выражений:
())(), )))(), )()(), )()(), )())), )())(.
Аналогичную процедуру можно проделать для остальных скобочных выражений и т.д. Все эти выражения можно огранизовать в дерево. В корне которого будет исходное выражение. Его детьми будут скобочные выражения с одной удаленной скобкой. Детьми детей будут выражения с еще одной удаленной скобкой и т.д. Это можно изобразить так:
Легко заметить, что на одном уровне такого дерева у нас все возможные скобочные выражения одного размера с одинаковым числом удаленных скобок. На первом уровне с одной удаленной скобкой. На втором с двумя и т.д.
В нашей задаче нужно найти все валидные скобочные выражения с минимальным числом удаленных скобок. Т.е. размер этих валидных выражений будет одинаковым и все они будут рассполагаться на одном уровне этого дерева. Поэтому для обхода дерева по уровням нам подойдет Поиск в Ширину.
Мы можем обходить дерево последовательно по уровням и проверять является ли скобочное выражение правильным. Если оно правильно, то нам нужно прекратить погружение в следующие уровни и просто дообработать текущий уровень в дереве.
Давайте сначала просто реализуем BFS для нашего случая: объявляем очередь. Кладем в очередь корень дерева. Далее в цикле пока очередь не пустая - достаем из головы очереди вершину. Если она валидная, то добавляем ее в результат. Для нее находим всех детей (в цикле по очереди удаляем первую, вторую и т.д. скобки). Кладем их в очередь.
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
Queue<String> queue = new ArrayDeque<>();
queue.add(s);
while (!queue.isEmpty()) {
String str = queue.poll();
if (isValid(str)) {
result.add(str);
}
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == ')') {
String candidate = str.substring(0, i) + str.substring(i + 1);
queue.add(candidate);
}
}
}
return result;
}
Улучшим решение при помощи трекинга уже проверенных ранее выражений, т.к. могут быть повторы. Это можно делать при помощи HashSet visited. Повторы изобразил одним цветом:
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
Queue<String> queue = new ArrayDeque<>();
queue.add(s);
Set<String> visited = new HashSet<>();
visited.add(s);
while (!queue.isEmpty()) {
String str = queue.poll();
if (isValid(str)) {
result.add(str);
}
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == ')') {
String candidate = str.substring(0, i) + str.substring(i + 1);
if (!visited.contains(candidate)) {
visited.add(candidate);
queue.add(candidate);
}
}
}
}
return result;
}
Наша текущая версия проходит все дерево от начала до конца. Т.е. все возможное комбинации. А нам нужно остановить погружение на следующие уровни, как только мы найдем первое правильное выражение. Поэтому добавим флаг found, чтобы предотвратить дальнейшее погружение. Более того, если на нашем уровне мы нашли валидное выражение и уже успели добавить какое-то число выражений следующего уровня, то они гарантированно будут не валидными. Т.к. выражение валидно, если у него четное число скобок. А на следующем уровне все выражения будут нечетного размера. Поэтому факт, что мы уже успели добавить какое-то число выражений следующего уровня не повляет на результат.
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
Queue<String> queue = new ArrayDeque<>();
queue.add(s);
Set<String> visited = new HashSet<>();
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
String str = queue.poll();
if (isValid(str)) {
result.add(str);
found = true;
}
if (found) continue;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == ')') {
String candidate = str.substring(0, i) + str.substring(i + 1);
if (!visited.contains(candidate)) {
visited.add(candidate);
queue.add(candidate);
}
}
}
}
return result;
}
Нам осталось реализовать функцию isValid. Более общая функция, которая проверят правильность скобочного выражения через стэк при наличии разного типа скобок описана тут: Проверить скобочное выражение. Но т.к. в нашей задаче только один вид скобок, то это можно упростить и не использовать стэк. А просто использовать счетчик:
private boolean isValid(String str) {
int count = 0;
for (char c : str.toCharArray()) {
if (c == '(') count++;
if (c == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
Если у нас открывающаяся скобка, то увеличиваем счетчик. Если закрывающая, то уменьшаем. Если в какой-то момент у нас счетчик меньше нуля - то выражение не валидно (Например, для выражения ")(" счетчик сначала станет -1, а потом ноль. Поэтому надо проверять на каждом шаге, а не только в конце). Если в конце счетчик не равен нулю, то есть несбалансированные скобки - выражение не валидно.
Финальная версия:
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
Queue<String> queue = new ArrayDeque<>();
queue.add(s);
Set<String> visited = new HashSet<>();
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
String str = queue.poll();
if (isValid(str)) {
result.add(str);
found = true;
}
if (found) continue;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == ')') {
String candidate = str.substring(0, i) + str.substring(i + 1);
if (!visited.contains(candidate)) {
visited.add(candidate);
queue.add(candidate);
}
}
}
}
return result;
}
private boolean isValid(String str) {
int count = 0;
for (char c : str.toCharArray()) {
if (c == '(') count++;
if (c == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
}
Временная сложность алгоритма зависит от числа вершин в нашем дереве. Как их можно посчитать? Т.к. мы рассматриваем все возможные комбинации, то для каждой из n скобок она может или присутствовать или отсутствовать. Т.е. для каждой скобки есть два варианта. Для двух скобок 4:
1) первая присутствует, вторая присутствует
2) первая отсутствует, вторая присутствует
3) первая присутствует, вторая отсутствует
4) первая отсутствует, вторая отсутствует
И т.д. для n скобок вариантов 2^n. Поэтому число вершин в нашем дереве 2^n. Временная сложность алгоритма O(n * 2^n). Дополнительное умножение на n возникает из-за того, что мы для каждой вершины проверяем ее валидность, что имеет сложность O(n). А также создаем новую строку candidate каждый раз, что также имеет сложность O(n).
Такая же сложность по памяти, т.к. нам надо хранить уже посещенные строки, длина одной ~n, всего строк 2^n. Поэтому сложность по памяти O(n * 2^n).
Существует более сложное для понимания рекурсивное решение этой задачи. Я оставлю разбор такого решения за рамками этой статьи.
Top comments (0)