Jewels and Stones

Q: Какова временная сложность задачи Jewels and Stones?

С множеством это O(j + s) : j шагов для создания множества из jewels и один поиск за постоянное время для каждого из s камней. Поиск по jewels для каждого камня — это O(j × s) .

Q: Сможешь решить это без множества?

Да. Буквы английские, поэтому массив из 128 или 256 флагов с индексами по кодам символов работает как множество без хеширования. Отметь букву каждого драгоценного камня, затем посчитай камни, для которых установлен флаг. Метод Ruby stones.count(jewels) выполняет всю работу за один вызов, но массив флагов показывает, что происходит внутри.

НовичокХеширование

+10

У тебя есть две строки из букв. Каждая буква в jewels обозначает один вид драгоценного камня, и ни одна буква не повторяется. Каждая буква в stones обозначает один камень, который у тебя есть. Верни количество твоих камней, которые являются драгоценными. Регистр букв имеет значение: "a" и "A" — это разные виды.

Функция

numJewelsInStones(jewels: string, stones: string) → integer

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

Ограничения

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Обе строки содержат только английские буквы, строчные и заглавные.
Все буквы в jewels разные.

Примеры

Ввод: jewels = "rR"stones = "rubyRRr"
Вывод: 4
Пояснение: Виды драгоценных камней — это r и R. В rubyRRr камни r, R, R и r подходят, а u, b и y — нет, поэтому ответ — 4.

Ввод: jewels = "z"stones = "ZZZ"
Вывод: 0
Пояснение: Единственный тип драгоценного камня — строчная буква z. Каждый камень — заглавная буква Z, это другой тип, поэтому ни один из них не считается.

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

Подсказки

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

Открыто 0 из 3

Решение

Для каждого камня нужен один ответ: является ли эта буква драгоценностью? Поиск в строке jewels для каждого камня снова и снова повторяет одно и то же сканирование. Один раз поместите буквы-драгоценности в множество, и проверка для каждого камня сведётся к одному поиску.

Просканируйте драгоценности и найдите каждый камень

Идея

Берите камни по одному. Для каждого камня просматривайте jewels и останавливайтесь на первой букве, которая ему соответствует. Совпадение увеличивает счётчик на 1. В первом примере камень u сравнивается с r и R, не находит совпадений и ничего не добавляет.

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

При j видах драгоценностей и s камнях потребуется до j × s сравнений. Здесь j ≤ 52, поэтому даже для 10^4 камней понадобится около 5 × 10^5 сравнений, и сканирование завершится вовремя. Неэффективность становится заметна, когда список видов растёт: для каждого камня поиск запускается заново.

Алгоритм

Установи count в значение 0.
Для каждого камня сравни его с каждой буквой в jewels.
При первом совпадении букв добавь 1 к count и переходи к следующему камню.
Верни count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Поместите драгоценности в набор

Идея

На вопрос «является ли эта буква драгоценной?» каждый раз будет один и тот же ответ, если задавать его об одной и той же букве. Поэтому ответь на него один раз для каждого вида: создай множество из букв jewels. Множество проверяет принадлежность за константное время, поэтому для каждого камня требуется одна проверка вместо перебора.

В первом примере множество — {r, R}. При переборе rubyRRr проверки дают ответы «да», «нет», «нет», «нет», «да», «да», «да»: четыре драгоценности. Создание множества занимает j шагов, а перебор — s, поэтому общая сложность равна O(j + s).

Множество содержит не более 52 букв. В языке без встроенного множества ту же задачу решает массив флагов, индексируемый кодом символа.

Алгоритм

Создай множество, содержащее все буквы из jewels.
Установи count равным 0.
Для каждого камня прибавляй 1 к count, если множество его содержит.
Верни count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

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

Алгоритм состоит из одного цикла. Неправильные ответы возникают из-за того, как сравниваются и подсчитываются буквы.

Игнорирование регистра. Перевод обеих строк в нижний регистр приводит к тому, что z совпадает с Z, и во втором примере возвращается 3 вместо 0.
Подсчёт различных видов драгоценностей вместо камней. В rubyRRr содержится два вида драгоценностей, но четыре драгоценных камня; учитывается каждый камень, включая повторяющиеся.
Создание множества внутри цикла по камням. Повторное создание множества для каждого камня требует j шагов каждый раз и возвращает сложность сканирования O(j × s). Создай множество один раз, до цикла.
Перестановка аргументов. Множество должно содержать jewels, а цикл должен проходить по stones. Если поменять их роли местами, во втором примере подсчитывается единственный вид драгоценности z среди камней, и результат всё равно равен 0, но ("a", "aaa") возвращает 1 вместо 3.

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

Какова временная сложность задачи Jewels and Stones?

С множеством это O(j + s): j шагов для создания множества из jewels и один поиск за постоянное время для каждого из s камней. Поиск по jewels для каждого камня — это O(j × s).

Зачем использовать хеш-множество для задачи «Драгоценности и камни»?

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

Сможешь решить это без множества?

Да. Буквы английские, поэтому массив из 128 или 256 флагов с индексами по кодам символов работает как множество без хеширования. Отметь букву каждого драгоценного камня, затем посчитай камни, для которых установлен флаг. Метод Ruby stones.count(jewels) выполняет всю работу за один вызов, но массив флагов показывает, что происходит внутри.

Python

def numJewelsInStones(jewels, stones):
    # Напишите код здесь

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

Случай 1

Случай 2

Ввод

jewels = "rR"
stones = "rubyRRr"

Ожидается