Вам даны строки J
, представляющие типы камней, которые являются драгоценностями, и S
, представляющие камни, которые у вас есть. Каждый символ в S
— это тип камня, который у вас есть. Вы хотите знать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы в J
гарантированно различаются, а все символы в J
и S
являются буквами. Буквы чувствительны к регистру, поэтому "a"
считается другим типом камня, чем "A"
.
Пример 1:
Input: J = "aA", S = "aAAbbbb" Output: 3
Пример 2:
Input: J = "z", S = "ZZ" Output: 0
Примечание.
S
иJ
будут состоять из букв и иметь длину не более 50.- Символы в
J
различны.
Подход
- Создайте хеш-таблицу с драгоценными камнями в качестве ключей и соответствующим количеством в качестве значений.
- Переберите строку камня, чтобы увидеть, есть ли в хэш-таблице запись для камня, и увеличьте счетчик, если да.
Реализация
Временная сложность: O(n)
Космическая сложность: O(n)