To Lower Case

Q: Как преобразовать строку в нижний регистр без встроенной функции?

Пройдитесь по символам и проверьте код каждого символа. Если код находится в диапазоне от 65 ( A ) до 90 ( Z ), прибавьте 32, чтобы получить строчную букву; все остальные символы оставьте без изменений. Снова объедините символы в строку.

Q: Почему разница между прописными и строчными буквами равна 32?

В ASCII заглавные буквы имеют коды от 65 до 90, а строчные — от 97 до 122; между ними расположены шесть символов. Оба алфавита идут в одном порядке, поэтому коды каждой пары отличаются на 97 - 65 = 32 . 32 — это один бит, поэтому установка этого бита превращает заглавную букву в соответствующую строчную.

Q: Можно ли изменить регистр с помощью побитовой операции?

Да. Для заглавной буквы code | 32 устанавливает бит, который различает два регистра, и даёт строчную букву, а code & ~32 снова сбрасывает его. Сначала всё равно нужно проверить диапазон, потому что тот же битовый приём изменит также цифры и символы.

Q: Какова временная сложность преобразования строки в нижний регистр?

Это O(n) для строки длины n , потому что каждый символ проверяется один раз. Новая строка занимает O(n) памяти. Если можно изменить массив символов на месте, дополнительная память сокращается до O(1) .

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

+10

Дана строка s. Верните новую строку, в которой каждая заглавная английская буква от A до Z заменена соответствующей строчной буквой. Все остальные символы, например строчные буквы, цифры и символы, остаются без изменений.

Функция

toLowerCase(s: string) → string

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

Ограничения

1 ≤ s.length ≤ 10⁴
Каждый символ s — это английская буква, цифра или один из символов !#$%&()*+-./:;<=>?@[]^_`{|}~.

Примеры

Ввод: s = "Hello-World!"
Вывод: "hello-world!"
Пояснение: Заглавные буквы H и W становятся строчными h и w. - и ! — не буквы, поэтому они остаются на своих местах.

Ввод: s = "coddy_2026"
Вывод: "coddy_2026"
Пояснение: Заглавной буквы для изменения нет. Строчные буквы, символ _ и цифры остаются без изменений.

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

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

Можешь написать toUpperCase с тем же циклом и объяснить, почему коды символов A и a отличаются всего на один бит?

Подсказки

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

Открыто 0 из 3

Решение

В каждом языке есть функция преобразования в нижний регистр, и в промышленном коде следует вызывать именно её. На собеседованиях задают эту задачу, чтобы проверить, знаете ли вы, как работает эта функция: символ — это число, а в ASCII код каждой заглавной буквы ровно на 32 меньше кода соответствующей строчной буквы. Проверьте, находится ли код между 'A' и 'Z', и прибавьте 32, если это так.

Вызовите встроенную функцию преобразования в нижний регистр

Идея

lower() в Python, toLowerCase() в JavaScript, downcase в Ruby и их аналоги в других языках уже выполняют эту задачу. В C и C++ есть tolower для одного символа, поэтому вы вызываете её в цикле. Каждый символ рассматривается один раз, поэтому трудоёмкость составляет O(n), а для новой строки требуется O(n) памяти.

Некоторые из этих функций учитывают языковые настройки компьютера. В турецком языке строчная буква для I — это ı без точки, а не i. Поэтому в версиях на Java и C# запрашивают фиксированное правило с помощью Locale.ROOT и ToLowerInvariant, чтобы результат не менялся от одного компьютера к другому.

В работе это правильный ответ. На собеседовании его часто не принимают, потому что он скрывает саму идею, о которой идёт речь в вопросе.

Алгоритм

Вызовите функцию преобразования в нижний регистр в вашем языке для s или примените tolower к каждому символу в C и C++.
Если функция это поддерживает, запросите фиксированное правило, не зависящее от языка.
Верните результат.

def toLowerCase(s):
    return s.lower()

Сдвигать коды символов заглавных букв

Идея

Каждый символ хранится в виде числа. В ASCII коды символов от A до Z — от 65 до 90, а от a до z — от 97 до 122. Обе последовательности идут в алфавитном порядке и начинаются с разницей в 32, поэтому код строчной буквы равен коду соответствующей заглавной плюс 32: H — это 72, а h — 104.

Поэтому пройдись по строке один раз. Если код находится в диапазоне от 65 до 90, прибавь 32; иначе скопируй символ без изменений. Проверка диапазона важна: символы [, ^ и _ находятся между Z и a, а @ стоит прямо перед A. Проверка только code < 97 превратила бы _ в другой символ.

Каждый символ проверяется один раз, значит, время выполнения — O(n). Результат — новая строка той же длины, занимающая O(n) памяти. Запись 'a' - 'A' вместо 32 означает то же самое и поясняет, откуда берётся это число.

Алгоритм

Скопируй s в массив символов или кодов.
Для каждой позиции прочитай код символа.
Если код находится между 'A' (65) и 'Z' (90), прибавь 32.
Преобразуй массив обратно в строку и верни её.

def toLowerCase(s):
    # Every capital letter sits 32 codes below its small letter: 'A' is 65, 'a' is 97.
    shift = ord("a") - ord("A")
    chars = []
    for ch in s:
        if "A" <= ch <= "Z":
            ch = chr(ord(ch) + shift)
        chars.append(ch)
    return "".join(chars)

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

Цикл короткий, поэтому ошибки связаны с проверкой диапазона и тем, как формируется ответ.

Прибавление 32 к каждому символу, который не является строчной буквой. Цифры и символы тоже изменятся: 1 превратится в Q.
Проверка только одного конца диапазона. code < 'a' также захватывает [, _ и @, а code >= 'A' также захватывает все строчные буквы.
Использование < вместо <= на границах оставляет A или Z заглавными.
Формирование ответа с помощью result = result + ch для неизменяемой строки. На каждом шаге копируется всё, что уже собрано, поэтому при n = 10^4 сложность квадратичная.
В C запись в исходные данные или забытый завершающий '\0'. Выделите для копии n + 1 байт.

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

Как преобразовать строку в нижний регистр без встроенной функции?

Пройдитесь по символам и проверьте код каждого символа. Если код находится в диапазоне от 65 (A) до 90 (Z), прибавьте 32, чтобы получить строчную букву; все остальные символы оставьте без изменений. Снова объедините символы в строку.

Почему разница между прописными и строчными буквами равна 32?

В ASCII заглавные буквы имеют коды от 65 до 90, а строчные — от 97 до 122; между ними расположены шесть символов. Оба алфавита идут в одном порядке, поэтому коды каждой пары отличаются на 97 - 65 = 32. 32 — это один бит, поэтому установка этого бита превращает заглавную букву в соответствующую строчную.

Можно ли изменить регистр с помощью побитовой операции?

Да. Для заглавной буквы code | 32 устанавливает бит, который различает два регистра, и даёт строчную букву, а code & ~32 снова сбрасывает его. Сначала всё равно нужно проверить диапазон, потому что тот же битовый приём изменит также цифры и символы.

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

Это O(n) для строки длины n, потому что каждый символ проверяется один раз. Новая строка занимает O(n) памяти. Если можно изменить массив символов на месте, дополнительная память сокращается до O(1).

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

s = "Hello-World!"

Ожидается

"hello-world!"