Remove Vowels

Q: Какова временная сложность удаления гласных?

Один проход занимает время O(n) , потому что для каждого символа выполняется проверка на гласную за постоянное время. В худшем случае для результата требуется O(n) памяти — когда в s вообще нет гласных. Вызов replace один раз для каждой гласной тоже занимает O(n) , но при этом строка считывается десять раз.

Q: Можешь удалить гласные с помощью регулярного выражения?

Да. Замена шаблона [aeiouAEIOU] на пустую строку выполняет это за один вызов в большинстве языков. Она работает за O(n) , как и цикл, но на собеседованиях обычно просят написать цикл, чтобы увидеть проверку гласных и то, как вы формируете результат.

НовичокМассивы и строки

+10

Вам дана строка s, состоящая из букв английского алфавита. Верните строку, полученную удалением всех гласных из неё. Гласные — это a, e, i, o и u, в нижнем или верхнем регистре; в данном случае y не является гласной. Оставшиеся буквы сохраняют свой порядок и регистр.

Функция

removeVowels(s: string) → string

sstring: строка английских букв для очистки
Возвращаетstring: s, из которой удалены все гласные, а остальные буквы оставлены в исходном порядке

Ограничения

1 ≤ s.length ≤ 3 × 10⁴
s содержит только английские буквы (a–z, A–Z).
s содержит хотя бы одну букву, которая не является гласной, поэтому ответ никогда не бывает пустым.

Примеры

Ввод: s = "Interview"
Вывод: "ntrvw"
Пояснение: Удаление I, e, i и e из Interview оставляет n, t, r, v, w в этом порядке. Заглавная I — это тоже гласная, поэтому она удаляется.

Ввод: s = "rhythm"
Вывод: "rhythm"
Пояснение: В rhythm нет a, e, i, o или u, поэтому ничего не удаляется. Буквы y нет в списке гласных, поэтому она остаётся.

Ввод: s = "EuropeanUnion"
Вывод: "rpnnn"
Пояснение: Восемь из тринадцати букв слова EuropeanUnion — гласные, включая заглавные E и U. Пять оставшихся согласных — r, p, n, n, n — сохраняют свой порядок и читаются как rpnnn.

+17 скрытых тестов при отправке

Дополнительный вопрос

Что, если текст мог бы содержать любую букву Unicode, например É или ö? Какие из них являются гласными и как изменится ваша проверка?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Удалять символы из середины строки по одному дорого, потому что всё после промежутка сдвигается. Лучше вместо этого собрать результат: пройти по строке один раз и скопировать каждую букву, которая не является гласной. Важно учесть заглавные гласные и то, как собирается результат.

Удалите каждую гласную за отдельный проход

Идея

Большинство языков могут удалить все вхождения одного символа из строки за один вызов: заменить его на пустую строку. Сделайте это десять раз — по одному разу для каждой из букв a e i o u A E I O U, и гласных не останется. Согласные не затрагиваются, поэтому они сохраняют свой порядок и регистр.

Для строки Interview проход для e даёт Intrviw, проход для i даёт Intrvw, а проход для I даёт ntrvw. Во время остальных семи проходов удалять нечего.

Каждый проход считывает всю текущую строку, поэтому требуется около 10n шагов по символам. Это всё ещё O(n), потому что десять — константа, но для 3 × 10^4 букв это означает 3 × 10^5 шагов, тогда как для одного прохода требуется 3 × 10^4.

Алгоритм

Берите десять букв, обозначающих гласные, aeiouAEIOU по одной.
Для каждой из них замените все её вхождения в s на пустую строку.
После десяти проходов верните то, что осталось от s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

Один проход, который сохраняет согласные

Идея

Поменяй задачу на противоположную: вместо удаления гласных собирай всё остальное. Один раз пройди по s и для каждого символа проверяй, является ли он одной из десяти букв гласных. Если нет, добавляй его в результат. Поскольку ты добавляешь символы в порядке чтения и никогда не меняешь их, порядок и регистр согласных останутся точно такими же, как во входной строке.

Для EuropeanUnion проход пропускает E, u, o, e, a, U, i и o, а добавляет r, p, n, n, n: результат — rpnnn.

Обработка каждого символа требует одной проверки за постоянное время (поиск в множестве, switch или поиск в строке из десяти букв), поэтому время работы составляет O(n). Собирай буквы в объекте StringBuilder или списке и в конце один раз преобразуй их в строку; наращивание неизменяемой строки с помощью += приводило бы к её копированию на каждом шаге. Сам результат занимает O(n) памяти.

Алгоритм

Создайте пустой буфер для результата.
Просматривайте s по одному символу за раз.
Если символ не входит в aeiouAEIOU, добавьте его в буфер.
Верните буфер в виде строки.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

Ловушки и крайние случаи

Большинство неправильных ответов связано с проверкой гласных или с тем, как растёт результирующая строка.

Забывают о заглавных гласных. Проверка только aeiou превращает Interview в Intrvw вместо ntrvw. Проверяй все десять букв или переводи символ в нижний регистр перед проверкой, а в результат добавляй исходный символ.
Изменяют регистр сохраняемых букв. Если перевести всю строку в нижний регистр, чтобы сократить проверку, QUEUEING превратится в qng вместо QNG. Переводи в нижний регистр только копию, которую проверяешь, а добавляй исходный символ.
Удаляют символы, проходя вперёд по индексам. Удаление s[i] сдвигает следующую букву на позицию i, а затем i++ пропускает её, поэтому вместо aab получается ab. Создавай новую строку или используй отдельные позиции чтения и записи.
Увеличивают неизменяемую строку с помощью += в цикле. В Java или C# на каждом шаге копируется вся строка — примерно 4.5 × 10^8 копирований символов для 3 × 10^4 букв. Используй построитель строк или список и объедини его один раз.

Частые вопросы4

Как удалить гласные из строки?

Пройдись по строке один раз и скопируй каждую букву, которая не является a, e, i, o или u (в любом регистре), в построитель строки или список. В конце объедини их в строку. Порядок и регистр сохранённых букв остаются такими же, как были.

Какова временная сложность удаления гласных?

Один проход занимает время O(n), потому что для каждого символа выполняется проверка на гласную за постоянное время. В худшем случае для результата требуется O(n) памяти — когда в s вообще нет гласных. Вызов replace один раз для каждой гласной тоже занимает O(n), но при этом строка считывается десять раз.

Можешь удалить гласные с помощью регулярного выражения?

Да. Замена шаблона [aeiouAEIOU] на пустую строку выполняет это за один вызов в большинстве языков. Она работает за O(n), как и цикл, но на собеседованиях обычно просят написать цикл, чтобы увидеть проверку гласных и то, как вы формируете результат.

Почему бы не удалить гласные из строки на месте?

Удаление одного символа из середины сдвигает все последующие символы влево, поэтому множество удалений может стоить O(n²). Это можно сделать на месте за O(n) с помощью двух индексов: один считывает каждый символ, а другой записывает следующую сохранённую букву, но в большинстве языков строки нельзя изменять, поэтому естественный способ — создать новую строку.

Python

def removeVowels(s):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "Interview"

Ожидается

"ntrvw"