Count Vowels

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

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

Q: Считается ли y гласной в этой задаче?

Нет. В английской орфографии y иногда выступает в роли гласной, как в слове rhythm , но в задачах по программированию гласными почти всегда считаются a , e , i , o и u , и в этой задаче именно так. Если в задаче есть y , добавь её к буквам, которые проверяешь.

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

+10

Тебе дана строка s, состоящая из английских букв. Посчитай, сколько в ней гласных, и верни это число. Гласные — это a, e, i, o и u, в нижнем или верхнем регистре. Буква y не считается.

Функция

countVowels(s: string) → integer

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

Ограничения

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

Примеры

Ввод: s = "Interview"
Вывод: 4
Пояснение: Гласные — это I, e, i и e. Заглавная I считается так же, как строчная, поэтому ответ — 4.

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

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

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

Можешь вернуть, сколько раз встречается каждая из пяти гласных, прочитав строку всего один раз?

Подсказки

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

Открыто 0 из 3

Решение

Подсчёт выполняется за один проход по строке с помощью счётчика. Нужно лишь решить, как проверять, является ли символ гласной, и что делать с заглавными буквами. Преобразуйте каждый символ в нижний регистр и сравните его с пятью гласными; обработка каждого символа требует постоянного объёма работы.

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

Идея

Разбейте вопрос на десять более простых: сколько букв a, сколько букв e и так далее до U. Каждое из этих чисел — обычный подсчёт. Пройдитесь по строке и прибавляйте 1 всякий раз, когда символ совпадает с искомой буквой, а затем сложите все десять чисел.

Каждая гласная в s совпадает ровно с одной из десяти букв в aeiouAEIOU, поэтому учитывается ровно один раз, а ни одна согласная не совпадает ни с одной из них. Для Interview проход для e находит 2, проход для i находит 1, проход для I находит 1, а в остальных семи проходах совпадений нет: всего 4.

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

Алгоритм

Задайте total = 0.
Берите десять букв aeiouAEIOU по одной.
Для каждой буквы пройдите всю строку и прибавляйте 1 к total каждый раз, когда символ совпадает с ней.
После десяти проходов верните total.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

Один проход с проверкой на строчные буквы

Идея

Поменяй циклы местами. Прочитай строку один раз и для каждого символа задай один вопрос: это гласная? Чтобы проверить оба регистра за один раз, сначала преобразуй символ в нижний регистр. I станет i, а E станет e, тогда как согласные останутся согласными, поэтому нужно сравнить символ только с пятью буквами: a, e, i, o и u.

Проверка выполняется за постоянное время: с помощью switch для пяти букв, поиска в множестве или поиска в строке из пяти букв aeiou. При проходе по строке Interview счётчик увеличивается на I, e, i и e и в итоге равен 4.

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

Алгоритм

Установи count = 0.
Проходи по строке по одному символу за раз.
Преобразуй символ в нижний регистр.
Если это a, e, i, o или u, увеличь count на 1.
Верни count.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

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

Задача решается в несколько строк, а ошибки возникают из-за случаев, которые не учитывает первая проверка.

Проверка только строчных букв. Сравнение только с aeiou не учитывает заглавную I в Interview и возвращает 3. Преобразуйте символ в нижний регистр или перечислите все десять букв.
Подсчёт y. В этой задаче y никогда не является гласной, поэтому для rhythm результат равен 0.
Считать индекс 0 отсутствием совпадения. "aeiou".indexOf('a') равен 0, что означает совпадение. Проверяйте на -1 или в PHP сравнивайте strpos со значением false с помощью !==, потому что там 0 == false.
Вызов strlen(s) в условии цикла в C. Функция проходит по всей строке на каждой итерации, поэтому для 5 × 10^4 символов требуется около 2.5 × 10^9 шагов. Остановитесь на терминаторе '\0' или вычислите длину один раз перед циклом.

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

Как посчитать количество гласных в строке?

Пройдите по строке один раз, используя счётчик. Преобразуйте каждый символ в нижний регистр и проверьте, является ли он a, e, i, o или u; если да, прибавьте 1. Когда цикл завершится, в счётчике будет ответ.

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

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

Считается ли y гласной в этой задаче?

Нет. В английской орфографии y иногда выступает в роли гласной, как в слове rhythm, но в задачах по программированию гласными почти всегда считаются a, e, i, o и u, и в этой задаче именно так. Если в задаче есть y, добавь её к буквам, которые проверяешь.

Для проверки гласной использовать множество, switch или поиск в строке?

Все три варианта состоят из пяти букв, выполняются за постоянное время на каждый символ, а разница в скорости между ними слишком мала, чтобы иметь значение. Выбирай тот, который лучше читается на твоём языке: switch в C, C++ или Go, множество или поиск в строке в Python, JavaScript или Ruby.

Python

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

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

Случай 1

Случай 2

Ввод

s = "Interview"

Ожидается