Reverse String

Решение

Подход

Это классическая задача на двухпоинтерную технику (two-pointer technique). Суть в том, что мы помещаем один указатель в начало, другой в конец, и свапиваем элементы, двигаясь друг к другу до встречи посередине.

Основное решение O(1) память

func reverseString(_ s: inout [String]) {
    var left = 0
    var right = s.count - 1
    
    while left < right {
        // Обмен элементами
        (s[left], s[right]) = (s[right], s[left])
        
        left += 1
        right -= 1
    }
}

Как это работает:

1. left указывает на начало, right на конец
2. Пока left < right, мы свапиваем элементы
3. Двигаемся навстречу друг другу
4. Когда встречаемся (left >= right), готово

Альтернативное решение с явным свопом

func reverseStringExplicit(_ s: inout [String]) {
    var left = 0
    var right = s.count - 1
    
    while left < right {
        let temp = s[left]
        s[left] = s[right]
        s[right] = temp
        
        left += 1
        right -= 1
    }
}

Этот вариант более явный и понятен тем, кто не знаком с tuple swapping в Swift.

Рекурсивное решение O(h) память (где h = высота рекурсии = n/2)

func reverseStringRecursive(_ s: inout [String], _ left: Int, _ right: Int) {
    // Базовый случай: встречаются в центре
    if left >= right {
        return
    }
    
    // Свапиваем элементы
    (s[left], s[right]) = (s[right], s[left])
    
    // Рекурсивно для остального массива
    reverseStringRecursive(&s, left + 1, right - 1)
}

// Вызов:
var chars = ["h", "e", "l", "l", "o"]
reverseStringRecursive(&chars, 0, chars.count - 1)

Тестирование

// Тест 1: Нечётное количество символов
var test1 = ["h", "e", "l", "l", "o"]
reverseString(&test1)
print(test1)  // ["o", "l", "l", "e", "h"]

// Тест 2: Палиндром
var test2 = ["H", "a", "n", "n", "a", "h"]
reverseString(&test2)
print(test2)  // ["h", "a", "n", "n", "a", "H"]

// Тест 3: Один символ
var test3 = ["a"]
reverseString(&test3)
print(test3)  // ["a"]

// Тест 4: Два символа
var test4 = ["a", "b"]
reverseString(&test4)
print(test4)  // ["b", "a"]

// Тест 5: Пустой массив (если допустимо)
var test5: [String] = []
reverseString(&test5)
print(test5)  // []

// Тест 6: Большой массив
var test6 = Array(1...1000).map { String($0) }
reverseString(&test6)
print(test6.first!, test6.last!)  // 1000, 1

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

Особенности Swift

1. Tuple Swapping: В Swift можно писать (a, b) = (b, a), это один из красивых синтаксисов языка:

var x = 5, y = 10
(x, y) = (y, x)  // x = 10, y = 5

1. inout параметр: Мы используем inout чтобы изменить исходный массив:

func modify(_ arr: inout [Int]) {
    arr[0] = 999
}

var numbers = [1, 2, 3]
modify(&numbers)
print(numbers)  // [999, 2, 3]

1. Диапазоны индексов: Swift не требует проверки границ как C, но нужно быть осторожным:

// Это безопасно благодаря типам
let arr = [1, 2, 3]
let first = arr[0]  // OK
// let invalid = arr[10]  // Runtime crash (но IDE предупредит)

Визуализация процесса

Исходный массив: [h, e, l, l, o]
Шаг 1: Swap (0, 4): [o, e, l, l, h], left=1, right=3
Шаг 2: Swap (1, 3): [o, l, l, e, h], left=2, right=2
Шаг 3: left == right, стоп
Результат: [o, l, l, e, h]

Вариации на собеседовании

Вопрос: Что если нужно работать со String, а не с массивом [String]? Ответ:

func reverseStringFromString(_ s: String) -> String {
    var chars = Array(s)  // Convert to array
    reverseString(&chars)
    return String(chars)
}

Вопрос: Работает ли с Unicode символами? Ответ: Работает, потому что мы просто меняем позиции. Swift Character правильно поддерживает Unicode.

Вопрос: Что если использовать без inout? Ответ:

func reverseStringWithoutInout(_ s: [String]) -> [String] {
    var result = s  // Копируем
    var left = 0
    var right = result.count - 1
    
    while left < right {
        (result[left], result[right]) = (result[right], result[left])
        left += 1
        right -= 1
    }
    
    return result
}

Но это создаст копию, не отвечает требованию "in-place".

Рекомендация для интервью

Используйте первое решение:

func reverseString(_ s: inout [String]) {
    var left = 0
    var right = s.count - 1
    
    while left < right {
        (s[left], s[right]) = (s[right], s[left])
        left += 1
        right -= 1
    }
}

Это:

• Показывает знание двухпоинтерной техники
• Демонстрирует понимание временной и пространственной сложности
• Использует идиоматичный Swift синтаксис
• Решает задачу оптимально