Реверс гласных в строке: метод двух указателей

Почему эта задача — ключ к пониманию алгоритмов

Вы когда-нибудь задумывались, почему на собеседованиях так любят задачи на строки? Задача LeetCode 345 «Reverse Vowels of a String» — это не просто упражнение для разминки. Она вскрывает сразу три важных навыка: умение работать с указателями, понимание неизменяемости строк и осознание важности Big-O. Освоив её, вы перестанете бояться подобных задач и увидите, как простые паттерны решают сложные на вид проблемы.

Постановка задачи

Нам дана строка, и нужно развернуть в ней только гласные буквы (a, e, i, o, u) в любом регистре. Согласные остаются на своих местах. Например, из "IceCreAm" должно получиться "AceCreIm".

Решение: метод двух указателей (схождение к центру)

Представьте строку как шеренгу людей. Один указатель ставим на первого (левый), другой — на последнего (правый). Двигаем их навстречу друг другу, пропуская согласные. Как только оба указателя указывают на гласные — меняем их местами. Продолжаем, пока указатели не встретятся.

Почему это работает? Гласные должны быть развёрнуты: первая слева меняется с первой справа, вторая слева — со второй справа и так далее. Два указателя идеально это реализуют.

Пошаговый разбор на примере

Возьмём строку "leetcode":

l e e t c o d e
0 1 2 3 4 5 6 7

Указатели: left = 0, right = 7. left двигается вправо, пока не найдёт гласную — это индекс 1 ('e'). right двигается влево, пока не найдёт гласную — это индекс 7 ('e'). Меняем местами — ничего не меняется, так как обе 'e'. Сдвигаем указатели: left = 2, right = 6. left на 'e' (гласная), right на 'd' — пропускаем, доходим до 'o' на индексе 5. Меняем 'e' и 'o' местами. Получаем "leotcede". Указатели сходятся, цикл завершён.

Реализация на Python

В Python строки неизменяемы, поэтому преобразуем строку в список символов. Вот полный код:

def reverse_vowels(s: str) -> str:
    # Множество гласных для быстрой проверки
    vowels = set('aeiouAEIOU')
    # Преобразуем строку в список для изменения
    chars = list(s)
    left, right = 0, len(s) - 1
    
    while left < right:
        # Пропускаем согласные слева
        if chars[left] not in vowels:
            left += 1
            continue
        # Пропускаем согласные справа
        if chars[right] not in vowels:
            right -= 1
            continue
        # Оба указателя на гласных — меняем
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    
    return ''.join(chars)

Разберём ключевые моменты:

• set для гласных обеспечивает проверку за O(1).
• Преобразование в список необходимо, так как строки неизменяемы.
• Условие left < right гарантирует остановку.
• Обмен через кортежную запись — идиоматично и лаконично.

Почему это эффективно: Big-O

Алгоритм проходит по строке один раз, каждый символ проверяется максимум один раз. Временная сложность — O(n), где n — длина строки. Дополнительная память — O(n) для списка символов, но это необходимо для изменяемости. Если бы мы работали только с чтением, можно было бы обойтись O(1), но здесь это не критично.

Частые ошибки и как их избежать

• Забыть про регистр: включайте в множество гласных и заглавные, и строчные.
• Неправильное условие цикла: используйте while left < right, а не <=, чтобы избежать лишней замены.
• Инкремент внутри условий: если пропускаете символ, не забудьте continue, чтобы не выполнить обмен.

Практический вывод

Прямо сейчас откройте LeetCode, найдите задачу 345 и решите её самостоятельно, не подглядывая. После этого попробуйте вариант с while циклами и проверьте, что код работает для строк с символами в разном регистре. Этот паттерн двух указателей пригодится вам во многих задачах: проверка палиндрома, поиск пар с суммой, разворот подстрок. Освоив его сегодня, вы сделаете большой шаг вперёд в подготовке к собеседованиям.