Проверьте, может ли регулярная последовательность скобок быть сформирована с конкатенацией заданных строк
Учитывая массив arr[] , состоящий из N строк, где каждая строка состоит из '(' и ')' , задача состоит в том, чтобы проверить, является ли регулярная последовательность скобок может быть образован конкатенацией заданных строк или нет. Если найдено верно, то выведите Yes . В противном случае выведите Нет .
Примеры:
Input: arr[] = { “)”, “()(” }
Output: Yes
Explanation: The valid string is S[1] + S[0] = “()()”.Input: arr[] = { “)(“, “()”}
Output: No
Explanation: No valid Regular bracket sequences are possible.
Подход: Данную задачу можно решить с помощью жадного подхода, основанного на следующих наблюдениях:
- Если строка содержит последовательную пару букв '(' и ')' , удаление этих двух букв не повлияет на результат.
- При повторении этой операции каждый S[i] становится (возможно, пустой) строкой, состоящей из 0 или более повторений ')', за которыми следует 0 или более повторений '(' .
- Тогда каждую строку можно обозначить двумя переменными A[i] = количество ')' и B[i] = количество '(' .
- Поддерживайте парный вектор v[][] для хранения этих значений.
- Теперь разделите две строки на два отдельных вектора pos[] и neg[] .
- pos[] будет хранить те строки, в которых общая сумма положительна , а neg[] хранить строки, общая сумма которых отрицательна .
- Теперь оптимальным способом является объединение сначала положительных строк, а затем отрицательных строк в порядке возрастания.
Выполните следующие шаги, чтобы решить проблему:
- Поддерживайте парный вектор v[][] , в котором будут храниться значения {сумма, минимальный префикс} , где сумма вычисляется как +1 для '(' и -1 для ')', а минимальный префикс является максимальным последовательным ') ' в строке.
- Итерация в диапазоне [0. N) с помощью переменной i и выполняем следующие шаги:
- Инициализируйте 2 переменные sum и pre как 0 , чтобы сохранить сумму и минимальный префикс для данной строки.
- Выполните итерацию в диапазоне [0, M) для каждого символа строки, и если текущий символ '(', то увеличьте сумму на 1 , иначе уменьшите ее на 1 и установите значение pre как минимум pre или sum в каждом шаг.
- Установите значение v[ I ] как {sum, pre}.
- Итерация в диапазоне [0. N) для элементов в v[] и для каждой пары, если сумма положительна, сохраните значение {-min_prefix, sum} в векторе pos[] иначе {sum – min_prefix, -sum} в векторе neg[] .
- Отсортируйте эти векторы в порядке возрастания.
- Инициализируйте переменную open как 0 .
- Итерация в диапазоне [0. size) , где size — это размер вектора pos[] с использованием переменной итератора p , а если open — p.first больше, чем равен 0 , то добавьте p.second к переменной open . В противном случае выведите No и вернитесь.
- Инициализируйте отрицательную переменную как 0 .
- Итерация в диапазоне [0. size) , где size — это размер вектора neg[] с использованием переменной итератора p , а если отрицательный — p.first больше, чем равен 0 , то добавьте p.second к отрицательной переменной. В противном случае выведите No и вернитесь.
- Если значение open не равно отрицательному , то выведите No. В противном случае выведите Да .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M + N*log(N)), где M — максимальная длина строки в массиве arr[].
Вспомогательное пространство: O(N)