Стремясь продолжать следовать моей практике LeetCode, я недавно сделал еще одно сообщение об этой проблеме из списка Challenges for New Users: «383. Выкуп записка".

Как и в случае с последней задачей, о которой я писал в разделе «Понимание LeetCode», это не требовало больших затрат времени, и, по крайней мере, для этого решения не требовалось глубокого понимания алгоритмов и структур данных.

Платформа под номером 383 попросит пользователя: «Учитывая две строки, ransomNote и magazine, вернуть true, если ransomNoteможет быть составлен с использованием букв из журнала и falseиначе». Далее следует «Каждая буква в журнале может быть использована в RansomNote только один раз».

Задача имеет два стандартных теста (при желании можно добавить больше):

Пример 1:

Ввод: ransomNote = «a», журнал: «b»
Вывод: false

Пример 2:

Ввод: ransomNote = «aa», журнал: «ab»
Вывод: false

Пример 3:

Ввод: ransomNote: «aa», журнал: «aab»
Вывод: true

Есть также два ограничения для решения проблемы:

  1. 1 ≤ ransomNote.length, magazine.length ≤ 10⁵, или длина обоих входных данных должна быть от 1 до 10⁵;
  2. ransomNote и magazine состоят из строчных букв латинского алфавита;

Исходный код, предоставленный платформой для построения функции, выглядит следующим образом:

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {};

Как обычно, я заменяю эту структуру на стрелочную функцию и использую константу вместо переменной для хранения функции, но это необязательный шаг. Прежде чем применять какую-либо логику, я хочу сначала проверить, существуют ли оба входа «ransomNote» и «magazine». Я знаю, что оба они также не нужны для решения, поскольку у нас уже есть два упомянутых выше ограничения, но было бы неплохо выработать привычку иметь такие проверки, когда мы пишем функцию с параметрами.

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
const canConstruct = (ransomNote, magazine) => {
    if (!ransomNote) return true;
    if (!magazine) return false;
};

Логика для этого проста и понятна: строка ransomNote должна повторяться с использованием цикла — мы используем цикл for — и для каждой итерации программа будет проверять, соответствует ли Строка magazine содержит ту же букву, что и анализируемая из ransomNote. Мы можем сделать это с помощью встроенной в JavaScript функции String.prototype.includes(). Если отклоненная проверка проходит успешно, что означает, что строка magazine не включает данную букву из строки ransomNote, программа вернет false.

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
const canConstruct = (ransomNote, magazine) => {
    if (!ransomNote) return true;
    if (!magazine) return false;

    for (let i = 0; i < ransomNote.length; i++) {
        if (!magazine.includes(ransomNote[i])) return false;
    }
};

В противном случае программа должна удалить указанную букву из строки магазина и продолжить цикл.

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
const canConstruct = (ransomNote, magazine) => {
    if (!ransomNote) return true;
    if (!magazine) return false;

    for (let i = 0; i < ransomNote.length; i++) {
        if (!magazine.includes(ransomNote[i])) return false;

        magazine = magazine.replace(ransomNote[i], "");
    }
};

Если программа может завершить цикл, это означает, что каждая буква в строке ransomNote может быть найдена внутри строки magazine. Для этого мы возвращаем true:

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
const canConstruct = (ransomNote, magazine) => {
    if (!ransomNote) return true;
    if (!magazine) return false;

    for (let i = 0; i < ransomNote.length; i++) {
        if (!magazine.includes(ransomNote[i])) return false;

        magazine = magazine.replace(ransomNote[i], "");
    }

    return true
};

Следует подчеркнуть, что это не должно быть окончательным или стандартным решением проблемы LeetCode 383, хотя в последний раз, когда я проверял, оно оказалось одним из самых популярных для JS.

Нашли ошибки в тексте выше? Скорее всего, вы это сделали, так как я написал и отредактировал его сам, поскольку не являюсь носителем английского языка, поэтому не стесняйтесь обращаться к ним, чтобы я мог улучшить его для следующих читателей. Это будет очень признательно.

Говори скорее,