Valid Parentheses
🇷🇺 Название: Допустимые скобки
LeetCode: valid-parentheses
Временная сложность: O(n)
Пространственная сложность: O(n)
Решение¶
class Solution:
def isValid(self, s: str) -> bool:
storage = []
valid = {
")": "(",
"]": "[",
"}": "{",
}
for char in s:
if char in valid.values():
storage.append(char)
elif char in valid.keys():
if not storage or valid[char] != storage.pop():
return False
return not storage
🇺🇸 Условие¶
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
🇷🇺 Условие¶
Примеры¶
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
{
"examples": [
{
"input": {
"s": "()"
},
"output": true
},
{
"input": {
"s": "()[]{}"
},
"output": true
},
{
"input": {
"s": "(]"
},
"output": false
},
{
"input": {
"s": "([])"
},
"output": true
}
]
}
Ограничения¶
- \(1 \leq s.length \leq 10^4\)
s
consists of parentheses only'()[]{}'
.
Потребление ресурсов¶
⏱ Time complexity: O(n)
¶
n
— длина строкиs
- Один проход по строке:
for char in s
—O(n)
- Все операции со стеком (
append
,pop
,not
) —O(1)
Итог: O(n)
🧠 Space complexity: O(n)
¶
- В худшем случае (все символы — открывающие скобки), стек
storage
будет содержатьn
элементов - Словарь
valid
— постоянного размераO(1)
Итог: O(n)
easy string stack
Metadata
- title_rus: Допустимые скобки
- difficulty: Easy
- leetcode_url: https://leetcode.com/problems/valid-parentheses/
- topics: ['String', 'Stack']
- time: O(n)
- space: O(n)
- grind75: True
- tags: ['Easy', 'Stack', 'String', 'problem']
- git_revision_date_localized: 5 июля 2025 г.
- git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_revision_date_localized_tag:
- git_revision_date_localized_raw_date: 5 июля 2025 г.
- git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_revision_date_localized_raw_iso_date: 2025-07-05
- git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_revision_date_localized_raw_timeago:
- git_revision_date_localized_raw_custom: 05. июля 2025
- git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_site_revision_date_localized_tag:
- git_site_revision_date_localized: 5 июля 2025 г.
- git_site_revision_date_localized_raw_date: 5 июля 2025 г.
- git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_site_revision_date_localized_raw_iso_date: 2025-07-05
- git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_site_revision_date_localized_raw_timeago:
- git_site_revision_date_localized_raw_custom: 05. июля 2025