📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1190. Reverse Substrings Between Each Pair of Parentheses
Сложность: medium

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"
Output: "dcba"

👨‍💻 Алгоритм:

1⃣Инициализируйте пустой стек openParenthesesIndices для отслеживания начальных точек разворота и пустую строку result для построения выходного результата.

2⃣Для каждого символа currentChar во входной строке:

Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.
Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.
В противном случае добавьте currentChar к result для построения строки.

3⃣Верните result как окончательную строку со всеми примененными разворотами.

😎 Решение:

class Solution:
    def reverseParentheses(self, s: str) -> str:
        openParenthesesIndices = []
        result = []

        for char in s:
            if char == '(':
                openParenthesesIndices.append(len(result))
            elif char == ')':
                start = openParenthesesIndices.pop()
                result[start:] = result[start:][::-1]
            else:
                result.append(char)

        return ''.join(result)

Ставь 👍 и забирай 📚 Базу знаний