< H / $ > Хак/Собесов

Перейти на PRO

Как перевернуть строку с минимальными затратами

«Как перевернуть строку с минимальными затратами» — вопрос из категории Алгоритмы и структуры данных, который задают на 25% собеседований C/C++ Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C/C++ Разработчик

Ответ

В C++ для строки типа std::string самый эффективный и идиоматичный способ — использовать алгоритм std::reverse из стандартной библиотеки. Он выполняет in-place разворот за линейное время O(n) и константную дополнительную память O(1).

#include <algorithm>
#include <string>
#include <iostream>

int main() {
    std::string str = "Hello, World!";
    std::reverse(str.begin(), str.end());
    std::cout << str << std::endl; // Вывод: "!dlroW ,olleH"
    return 0;
}

Почему это минимальные затраты:

Время: O(n) — меньше нельзя, нужно посетить каждый символ.
Память: O(1) — алгоритм использует два итератора и меняет символы местами, не создавая новую строку.
Оптимизация: Реализация std::reverse в стандартной библиотеке часто использует оптимизации для конкретного компилятора.

Для C-строк (массивов char) принцип тот же, но реализуется вручную:

#include <cstring>

void reverse_c_string(char* str) {
    if (!str) return;
    char* end = str + strlen(str) - 1;
    while (str < end) {
        std::swap(*str, *end); // или ручной обмен через временную переменную
        ++str;
        --end;
    }
}