Описание испытания.

Учитывая две строки 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;
}