Valid Parentheses

Решение: Valid Parentheses на Swift

Основное решение со стеком

func isValid(_ s: String) -> Bool {
    var stack: [Character] = []
    let pairs: [Character: Character] = [
        ")": "(",
        "}": "{",
        "]": "["
    ]
    
    for char in s {
        if pairs.keys.contains(char) {
            if stack.isEmpty || stack.removeLast() != pairs[char] {
                return false
            }
        } else {
            stack.append(char)
        }
    }
    
    return stack.isEmpty
}

Объяснение алгоритма

Логика: Используем стек для хранения открывающих скобок. При встречи открывающей скобки добавляем в стек. При встречи закрывающей скобки проверяем, что последняя открывающая скобка совпадает по типу. В конце стек должен быть пуст.

Сложность: O(n) время, O(n) память в худшем случае (только открывающие скобки).

Пошаговый пример: "([)]"

Итерация 1: "(" → стек = ["("] Итерация 2: "[" → стек = ["(", "["] Итерация 3: ")" → ожидаем "[", но получили "(" → return false

Альтернативное решение с guard

func isValid(_ s: String) -> Bool {
    var stack: [Character] = []
    let closingToOpening: [Character: Character] = [
        ")": "(", "}": "{", "]": "["
    ]
    
    for char in s {
        if let matchingOpen = closingToOpening[char] {
            guard !stack.isEmpty, stack.last == matchingOpen else {
                return false
            }
            stack.removeLast()
        } else {
            stack.append(char)
        }
    }
    return stack.isEmpty
}

Оптимизация для iOS

• Быстрая проверка нечётной длины: если count % 2 != 0, то return false
• reserveCapacity(s.count / 2) для оптимизации аллокаций памяти
• Избегаем многократного пересчёта length

Юнит-тесты

• testSimpleValid: "()" → true, "{}" → true, "[]" → true
• testComplex: "()[]{}", "{[]}" → true
• testInvalid: "(]" → false, "([)]" → false
• testEdgeCases: "(" → false, ")" → false, "" → true
• testNested: "((()))" → true, "[[[{}]]]" → true
• testLongString: 1000 повторений → true, 5000 открывающих → false

Анализ сложности

Временная: O(n) — один проход по строке Пространственная: O(n) в худшем случае (стек до n/2 элементов) Лучший случай: O(n) → "()" одной элемент Худший случай: O(n) → "(((((" стек содержит всё