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.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

Строка читается десять раз. Это всё ещё 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, а согласные останутся согласными, и тебе нужно будет сравнивать символы с пятью буквами, а не с десятью.

Проверка выполняется за постоянное время: с помощью switch, поиска в множестве или поиска в строке aeiou. Каждый символ считывается один раз, и хранится только счётчик: время — 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. Здесь она никогда не является гласной, поэтому rhythm даёт 0.
Считать индекс 0 отсутствием совпадения. "aeiou".indexOf('a') равно 0, что означает совпадение. Проверяй на -1 или в PHP сравнивай strpos с false с помощью !==, потому что там 0 == false.
Вызов strlen(s) в условии цикла на C. Он повторно сканирует строку на каждом шаге, поэтому для 5 × 10^4 символов требуется около 2.5 × 10^9 шагов.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Аргумент

s = "Interview"

Ожидаемый вывод