Проверьте, может ли регулярная последовательность скобок быть сформирована с конкатенацией заданных строк

Опубликовано: 21 Сентября, 2022

Учитывая массив 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ