Ransom Note

Лёгкая№383подсчёт

Даны записка и журнал. Нужно понять, можно ли сложить записку из букв, вырезанных из журнала, если каждую букву журнала можно взять только один раз. Наш пример: записка «hello» и журнал «shelfloor» — да, и ещё останутся s, f, r и одна o.

383 Ransom NoteРазбор · 1×

Пример: записка «hello», журнал «shelfloor». Под ними — словарь: буква и сколько таких ещё осталось в журнале.

magazinenoteshelfloorhellocount—
ещё не дошлитекущая буквапосчитано, ещё естькончиласьне хватаетзаписка собрана

Начинаем с пустого словаря: у каждой буквы счётчик 0

01/35
сначала · назад · пуск · шаг
Скорость
1function canConstruct(note, magazine):
2 count = empty map // missing keys: 0
3 for each c in magazine:
4 count[c] = count[c] + 1
5 for each c in note:
6 count[c] = count[c] - 1
7 if count[c] < 0:
8 return false
9 return true
состояние
count
{}
c
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждую букву журнала можно взять один раз, а где она стоит, неважно. Значит, нужно знать только, сколько каких букв в журнале: сначала их считаем.
  2. Записка тратит буквы: минус единица за каждую свою букву. Счётчик ниже 0 — записке нужна буква, которой в журнале уже нет: сразу false.
  3. Если вся записка потрачена и ничего не ушло ниже 0, все буквы нашлись: true. Лишние буквы журнала не мешают.

Сложность

Время O(m + n): один проход по журналу и один по записке. Память O(1): для строчных букв не больше 26 счётчиков.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.