Заключите заданные подстроки строки в круглые скобки

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

Имея строку S и список строк subs[] , в котором хранятся подстроки S, и все подстроки присутствуют только один раз, задача состоит в том, чтобы заключить подстроки S , существующие в subs[] , в круглые скобки. Если подстроки в subs[] перекрывают друг друга или идут подряд, то объединяем их в один набор круглых скобок.

Примеры:

Input: S = “abcdefgh”, subs = {“ef”, “bc”, “g”}
Output: “a(bc)d(efg)h”
Explanation: Substrings “ef” and “g” are consecutive. 
So they are enclosed within one set of parentheses.
Substring “bc” is enclosed within one set of parentheses

Input: S = “abcdefgh”, subs = [“abcde”, “bc”]
Output: “(abcde)fgh”
Explanation: Substrings “abcde” and “bc” overlap. 
So they are enclosed within one set of parentheses.

Подход: Идея решения проблемы заключается в следующем:

We can find the starting and ending index of each substring of subs[] in the string S. Then they can be considered as separate intervals and we can use the concept of merging overlapping intervals to merge them and enclose them in parentheses.

Для реализации идеи выполните следующие шаги:

  • Создайте список для хранения позиций открытия и закрытия каждой подстроки subs[].
  • Объедините эти интервалы открытия и закрытия позиций. Для этого сделайте следующее:
    • Отсортировать все интервалы по открытию позиции в порядке возрастания.
    • Начиная с первого интервала, пройдите отсортированные интервалы и выполните следующие действия для каждого интервала:
      • Если текущий интервал не является начальным интервалом и перекрывается с предыдущим интервалом, объедините их вместе.
      • Если нет, добавьте текущий интервал в список выходных интервалов.
  • Просмотрите объединенный список интервалов и вставьте соответствующие скобки в строку S .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*logN + N*M), где N — размер subs[], а M — длина S
Вспомогательное пространство: O(N)

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