Условие

Дана строка s, состоящая из слов, разделенных одним пробелом. Требуется перевернуть все символы в каждом слове, сохраняя порядок слов и пробелы между ними.

Примеры

Input: s = "Let's take LeetCode contest” Output: "s'teL ekat edoCteeL tsetnoc”

Input: s = "Mr Ding” Output: "rM gniD”

Решение

fun reverseWords(s: String): String {
    val chars = s.toCharArray()
    var start = 0

    // Вспомогательная функция для переворота части массива символов
    fun reverse(start: Int, end: Int) {
        var left = start
        var right = end
        // Переворачиваем подстроку от left до right
        while (left < right) {
            // Меняем местами символы
            val temp = chars[left]
            chars[left] = chars[right]
            chars[right] = temp
            left++
            right--
        }
    }

    // Проходим по всей строке
    for (i in chars.indices) {
        // Если встречаем пробел или достигли конца строки
        if (chars[i] == ' ' || i == chars.size - 1) {
            // Определяем конец текущего слова
            val end = if (chars[i] == ' ') i - 1 else i
            // Переворачиваем текущее слово
            reverse(start, end)
            // Устанавливаем начало следующего слова
            start = i + 1
        }
    }

    // Преобразуем измененный массив символов обратно в строку
    return String(chars)
}

Временная сложность

O(n) — Один проход по строке длины n и переворот каждого слова.

Пространственная сложность

O(1) — Используется дополнительная память только для изменения строки на месте.