Стремясь продолжать следовать моей практике 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 ≤ ransomNote.length, magazine.length ≤ 10⁵, или длина обоих входных данных должна быть от 1 до 10⁵;
- 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.
Нашли ошибки в тексте выше? Скорее всего, вы это сделали, так как я написал и отредактировал его сам, поскольку не являюсь носителем английского языка, поэтому не стесняйтесь обращаться к ним, чтобы я мог улучшить его для следующих читателей. Это будет очень признательно.
Говори скорее,