Дано: Задана строка s, содержащая только символы '(', ')', '{', '}', '[' и ']'. Определите, является ли эта строка корректной.
Уточнение:
Строка является корректной, если:
- открытые скобки закрыты скобками того же типа,
- скобки должны быть закрыты в правильном типовом порядке,
- каждая закрытая скобка имеет соответствующую открытую скобку того же типа.
Пример:
Вход: s = "()[]{}"
Выход: true
Ограничения:
1 <= s.length <= 104
s состоит только из скобок вида: '()[]{}'.
Решение(Python):
1) С помощью replace
def isValid(s: str) -> bool:
while len(s) > 0:
l = len(s)
s = s.replace('()','').replace('{}','').replace('[]','')
if l==len(s): return False
return True
Интересный вариант, прогоняем нашу строку в цикле, пока не уничтожим все скобки, или не найдем совпадений по replace.. Допустим есть строка "{[]}", то есть s.replace('()','').replace('{}','').replace('[]','') всегда будет вычищать внутренние скобки, если таковы имеются, после первого прохода мы получим "{}" и вторым проходом уничтожим и фигурные скобки "{}", выдавая True в ответе.
Временная сложность: replace O(n?) в циклe O(n) дает нам сложность O(n^2)
Пространственная сложность: O(1)
2) С помощью свойств стека.
Метод pop() удаляет элемент по индексу и возвращает его. Если не указывать параметры, то будет удален последний элемент
def isValid(s: str) -> bool:
stack= []
for i in s:
if i in ['(', '{', '[']:
stack.append(c)
elif i == ')' and len(stack) != 0 and stack[-1] == '(':
stack.pop()
elif i == '}' and len(stack) != 0 and stack[-1] == '{':
stack.pop()
elif i == ']' and len(stack) != 0 and stack[-1] == '[':
stack.pop()
else:
return False
return stack== []
Создаём список для оперирования строкой leftSymbols. Пройдем по строке циклом слева направо. Если встретится открытая скобка, то мы поместим ее в список leftSymbols. Если встречается закрытая скобка, то мы сверяем ее с последним элементом [-1] списка leftSymbols. Если это скобка того же типа, то мы удаляем открывающую скобку и переходим дальше, иначе возвращаем false.
Улучшение:
def isValid(s: str) -> bool:
parenthesis= {'(': ')', '{': '}', '[': ']'}
stack = []
for i in s:
if i in parenthesis:
stack.append(i)
elif len(stack) == 0 or parenthesis[stack.pop()] != i:
return False
return stack== []
Заменяем три elif в предыдущем варианте на один: если правая скобка и стек пуст (значит, нет совпадающей левой скобки), или последняя левая скобка в списке не совпадает с текущим i, то есть правой скобкой, возвращаем False.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем список, дающий нам сложность O(n)
