Описание испытания.
Учитывая две строки ransomNote
и magazine
, вернуть true
, еслиransomNote
можно составить, используя буквы изmagazine
иfalse
в противном случае.
Каждая буква в magazine
может использоваться только один раз в ransomNote
.
Пример 1:
Input: ransomNote = "a", magazine = "b" Output: false
Пример 2:
Input: ransomNote = "aa", magazine = "ab" Output: false
Пример 3:
Input: ransomNote = "aa", magazine = "aab" Output: true
Интуиция
Здесь я предполагаю, что ransomNote обозначен как «t», а журнал — как «s», просто чтобы не усложнять и дать хорошее объяснение. Я также использовал то же самое в своем коде.
А теперь, ребята, как думать?
Просто посмотрите, чтобы сделать строку t из s, у нас должно быть достаточное количество символов в s. Как вести их счет?? 🧐
ответ: используйте карту, которая хранит ‹char,вхождение в строке s›.
шаги, чтобы следовать:
шаг 1:
заполните вашу карту с помощью повторяющейся строки s, т.е. журнала, чтобы получить количество вхождений каждого символа.
шаг 2:
теперь перебираем строку t, т. е. ransomNote, и проверяем, достаточно ли у вас символов в s для каждого символа, если да, то просто возьмите его и уменьшите с карты, поскольку вы использовали его.
Если у вас недостаточно символов, верните false. ❌
если все остается в порядке до конца, просто верните true ✅ .
Сложность
- Временная сложность: O(N) + O(M) ~ O(max(N,M))
Для каждой итерации по длине строки.
- Пространственная сложность: O(N) для карты
function canConstruct(t: string, s: string): boolean { const mp: Map<string, number> = new Map(); for (let i = 0; i < s.length; i++) { const char = s.charAt(i); mp.set(char, (mp.get(char) || 0) + 1); } for (let i = 0; i < t.length; i++) { const char = t.charAt(i); if (mp.get(char) && mp.get(char)! > 0) { mp.set(char, mp.get(char)! - 1); } else { return false; } } return true; }