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

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

Для заданной числовой строки S , состоящей только из символов '1', '2' и '3' , задача состоит в том, чтобы заменить символы либо открывающей скобкой ( '(' ), либо закрывающей скобкой ( ')' ), чтобы вновь сформированная строка становится сбалансированной скобочной последовательностью.

Примечание. Все вхождения символа должны быть заменены одинаковыми круглыми скобками.

Примеры:

Input: S = “1123”
Output: Yes, (())
Explanation: Replacing occurrences of character ‘1’ with ‘(‘, ‘2’ with ‘)’ and ‘3’ with ‘)’. Therefore, the obtained bracket sequence is “(())”, which is balanced.

Input: S = “1121”
Output: No

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • Для сбалансированной последовательности скобок необходимо, чтобы первый и последний символы были соответственно открывающими и закрывающимися скобками. Поэтому первый и последний символы должны быть разными.
  • Если первый и последний символы строки совпадают, то невозможно получить сбалансированную последовательность скобок.
  • Если первый и последний символы строки различны, то они заменяются соответственно открывающими и закрывающимися скобками. Третий символ заменяется либо открывающими , либо закрывающимися скобками.
  • Проверьте оба способа замены один за другим для оставшегося третьего символа.
  • Если обе замены третьего оставшегося символа не могут составить сбалансированную последовательность скобок, то невозможно создать сбалансированную последовательность скобок.

Выполните следующие шаги, чтобы решить данную проблему:

  • Проверьте, равны ли первый и последний символы строки S. Если окажется, что это правда, то выведите «Нет» и вернитесь.
  • Инициализируйте две переменные, скажем, cntforOpen и cntforClose , чтобы хранить количество открытых и закрытых скобок.
  • Переберите символы строки и выполните следующие операции:
    • Если текущий символ совпадает с первым символом строки, увеличьте значение cntforOpen.
    • Если текущий символ совпадает с последним символом строки, уменьшите cntforOpen.
    • Для оставшегося третьего символа увеличьте cntforOpen , то есть замените этот символ на '(' .
    • Если в какой-то момент cntforOpen окажется отрицательным, то сбалансированная скобочная последовательность не может быть получена.
  • Аналогично проверьте с помощью переменной cntforClose , т.е. заменив третий символ на ')' .
  • Если ни один из двух вышеперечисленных методов не генерирует сбалансированную последовательность скобок, выведите «No» . В противном случае выведите «Да».

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

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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