Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
👨💻 Алгоритм:
1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.
2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.
3⃣Создайте новую строку, удалив все помеченные скобки.
😎 Решение:
def minRemoveToMakeValid(s):
stack = []
s = list(s)
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
elif s[i] == ')':
if stack:
stack.pop()
else:
s[i] = ''
while stack:
s[stack.pop()] = ''
return ''.join(s)
Ставь 👍 и забирай 📚 Базу знаний