Разворот строки

Разворот строки

Задача: Перевернуть строку без использования встроенных функций reverse() или срезов [::-1].

Решение 1: Цикл в обратном порядке

Проходим по строке от конца к началу:

def reverse_string(s: str) -> str:
    """
    Переворачивает строку через цикл.
    """
    result = ""
    for i in range(len(s) - 1, -1, -1):
        result += s[i]
    return result

# Тестирование
test_cases = [
    ("hello", "olleh"),
    ("Python", "nohtyP"),
    ("a", "a"),
    ("", ""),
    ("12345", "54321"),
    ("abc", "cba"),
]

for input_str, expected in test_cases:
    result = reverse_string(input_str)
    status = "✓" if result == expected else "✗"
    print(f"{status} reverse_string('{input_str}') = '{result}'")

Сложность:

• Время: O(n) — проходим по каждому символу один раз
• Память: O(n) — создаём новую строку

Минус: В Python конкатенация строк неэффективна, так как создаёт новый объект каждый раз.

Решение 2: Со списком (более эффективно)

Используем список для конкатенации (список изменяемый):

def reverse_string(s: str) -> str:
    """
    Переворачивает строку через список (эффективнее).
    """
    chars = list(s)  # Преобразуем в список
    reversed_chars = []
    
    # Проходим от конца к началу
    for i in range(len(chars) - 1, -1, -1):
        reversed_chars.append(chars[i])
    
    # Объединяем обратно в строку
    return "".join(reversed_chars)

# Тестирование
for input_str, expected in test_cases:
    result = reverse_string(input_str)
    status = "✓" if result == expected else "✗"
    print(f"{status} reverse_string('{input_str}') = '{result}'")

Почему эффективнее?

• append() — O(1) амортизированная операция
• join() — O(n) единовременная операция
• Лучше, чем множественные конкатенации

Решение 3: Две указатели (in-place с логикой)

Хотя Python не поддерживает true in-place для строк, можем имитировать логику двух указателей:

def reverse_string(s: str) -> str:
    """
    Логика двух указателей (как в C/Java with char array).
    """
    chars = list(s)  # Преобразуем в список
    left, right = 0, len(chars) - 1
    
    # Обменяем элементы с обоих концов
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    
    return "".join(chars)

# Тестирование
for input_str, expected in test_cases:
    result = reverse_string(input_str)
    status = "✓" if result == expected else "✗"
    print(f"{status} reverse_string('{input_str}') = '{result}'")

Пример для "hello":

Шаг 1: left=0, right=4
  chars = ['h','e','l','l','o'] → ['o','e','l','l','h']
  left=1, right=3

Шаг 2: left=1, right=3
  chars = ['o','e','l','l','h'] → ['o','l','l','e','h']
  left=2, right=2

Стоп: left >= right
Результат: "olleh"

Сложность:

• Время: O(n)
• Память: O(n) для списка

Решение 4: Рекурсия

Используем рекурсию для разворота:

def reverse_string(s: str) -> str:
    """
    Рекурсивное решение.
    """
    # Базовый случай: пустая или одна буква
    if len(s) <= 1:
        return s
    
    # Рекурсивный случай
    # Берём последний символ + рекурсивно разворачиваем остаток
    return reverse_string(s[1:]) + s[0]

# Тестирование
for input_str, expected in test_cases:
    result = reverse_string(input_str)
    status = "✓" if result == expected else "✗"
    print(f"{status} reverse_string('{input_str}') = '{result}'")

Как это работает для "hello":

reverse("hello")
  = reverse("ello") + "h"
    = (reverse("llo") + "e") + "h"
      = ((reverse("lo") + "l") + "e") + "h"
        = (((reverse("o") + "l") + "e") + "h"
          = ((("o" + "l") + "e") + "h")
            = (("ol" + "e") + "h")
              = ("ole" + "h")
                = "oleh"

Сложность:

• Время: O(n)
• Память: O(n) для стека вызовов + новые строки

Минус: Медленнее из-за срезов s[1:] и конкатенаций.

Решение 5: Stack (классическое)

Используем стек (в Python это список):

def reverse_string(s: str) -> str:
    """
    Решение со стеком.
    """
    stack = list(s)  # Стек = список символов
    result = ""
    
    # Извлекаем символы со стека (LIFO)
    while stack:
        result += stack.pop()  # pop() удаляет и возвращает последний элемент
    
    return result

# Тестирование
for input_str, expected in test_cases:
    result = reverse_string(input_str)
    status = "✓" if result == expected else "✗"
    print(f"{status} reverse_string('{input_str}') = '{result}'")

Это классический пример использования стека.

Сравнение решений

import timeit

test_string = "a" * 10000  # Большая строка

# Тест производительности
print("Бенчмарк (10000 итераций):")
print()

time1 = timeit.timeit(
    lambda: reverse_string_loop(test_string),
    number=10000
)
print(f"1. Цикл: {time1:.4f}s")

time2 = timeit.timeit(
    lambda: reverse_string_list(test_string),
    number=10000
)
print(f"2. Список: {time2:.4f}s")

time3 = timeit.timeit(
    lambda: reverse_string_two_pointers(test_string),
    number=10000
)
print(f"3. Два указателя: {time3:.4f}s")

time5 = timeit.timeit(
    lambda: reverse_string_stack(test_string),
    number=10000
)
print(f"5. Stack: {time5:.4f}s")

print()
print("Рекурсия не включена (может быть медленной/переполнить стек)")

Практические рекомендации

Для интервью:

• Начните с решения 1 (цикл) — самое простое объяснить
• Затем оптимизируйте в решение 2 (список + join)
• Если попросят in-place логику — используйте решение 3 (два указателя)

Для production:

• Просто используйте встроенный способ: s[::-1] или reversed(s)
• Это оптимизировано на уровне C

# Production код
def reverse_string(s: str) -> str:
    return s[::-1]  # Или: ''.join(reversed(s))

Граничные случаи

def test_edge_cases():
    assert reverse_string("") == ""  # Пустая строка
    assert reverse_string("a") == "a"  # Один символ
    assert reverse_string("ab") == "ba"  # Два символа
    assert reverse_string("123") == "321"  # Цифры
    assert reverse_string("Hello, World!") == "!dlroW ,olleH"  # Спецсимволы
    assert reverse_string("   ") == "   "  # Пробелы
    assert reverse_string("🎉😀") == "😀🎉"  # Unicode/Эмодзи
    print("Все тесты пройдены!")

test_edge_cases()

Итоговая рекомендация

Для этой задачи наиболее оптимальное и понятное решение — два указателя (Решение 3), так как:

• Простое логическое объяснение
• O(n) время и O(n) память
• Демонстрирует понимание манипуляции данными
• Подход работает и в других языках (C, Java, C++)