Задача про скобки.
Супер распространенная задача со скрининг-собеседований.
На вход подается строка, состоящая из круглых скобок. Выведите
Например, если входная строка
А если
Это базовая задача на алгоритмы и решается она за один проход по строке (O(n)). Идея здесь следующая: нужно завести переменную-стек, которая будет хранить состояние скобки на i-том шаге и в зависимости от состояния принимать решение о том, валидная строка или нет.
Вот видео с более подробным описанием решения.
Вот возможное решение:
Можете решить ее самостоятельно.
Супер распространенная задача со скрининг-собеседований.
На вход подается строка, состоящая из круглых скобок. Выведите
True, если скобки вложены правильно и False, если нет.Например, если входная строка
(()(())), то ответ должен быть True. А если
()), то False. Это базовая задача на алгоритмы и решается она за один проход по строке (O(n)). Идея здесь следующая: нужно завести переменную-стек, которая будет хранить состояние скобки на i-том шаге и в зависимости от состояния принимать решение о том, валидная строка или нет.
Вот видео с более подробным описанием решения.
Вот возможное решение:
def if_balanced(string):
stack = []
for i in string:
if i == "(":
stack.append(i)
elif i == ")":
if not stack:
return False
stack.pop()
if stack:
return False
return True
print(if_balanced("()()())"))
Усложненная форма этой же задачи: на вход подаются строка со скобками разных видов, например, ([]{}) -> True, ({}([]{)}) -> False. Можете решить ее самостоятельно.