Потому что обычного старого палиндрома недостаточно. Пошаговое руководство по решению проблемы алгоритма шумного палиндрома с использованием ASCII в JavaScript.

«Обычный палиндром было бы слишком просто, не так ли?» - никогда в жизни никто не говорил.

Что ж, это, вероятно, ложь, но вы поняли мою мысль. Если вы, как и я, проводите время на разных сайтах, решая разные упражнения по кодированию, вы, скорее всего, столкнетесь с классическим вопросом о палиндроме, когда вас спрашивают, является ли строка палиндромом.

Если нет, не беспокойтесь! Проблема, которую я немного расскажу, добавляет лишь небольшой уровень сложности к этой классической проблеме, при этом решение по-прежнему охватывает то, как мы проверяем, является ли строка палиндромом после того, как мы изменим ввод.

Палиндром, как напоминание, - это слово, фраза, стих или предложение, которое читается одинаково вперед или назад. Примерами палиндрома являются «мадам» и «гоночная машина». Оба эти слова читаются одинаково независимо от того, идете ли вы слева направо или справа налево.

Так что же за шумный палиндром? Рад, что вы спросили - приступим!

Эта проблема

Проблема заключается в следующем:

Вам дается строка s, содержащая символы алфавита в нижнем и верхнем регистре, а также цифры от «0» до «9». Верните, является ли s палиндромом, если мы рассматриваем только символы нижнего регистра алфавита.

Хорошо, там много чего происходит. Таким образом, мы не только работаем с алфавитными символами в нашей строке ввода, но и с числами, которые сбивают нас с толку. Что еще хуже, мы также должны позаботиться о прописных буквах алфавита! Блин.

Итак, что было бы за шумный палиндром? Давайте посмотрим на пару примеров:

  1. «A92bcbXa»
  2. «4567abcDO»

Наш первый пример - палиндром. Если мы смотрим только на строчные буквы алфавита и удаляем все остальное, наша строка будет выглядеть как «abcba». Он читает то же самое вперед и назад, поэтому это палиндром.

Наш второй пример - НЕ палиндром. Опять же, если мы смотрим только на строчные буквы алфавита и удаляем все остальное, наша строка будет выглядеть как «abc». Поскольку наша строка не читает одно и то же вперед и назад, это не палиндром.

Большой! Мы понимаем проблему, так как мы можем подойти к ней?

Подход

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

Но что, если бы мы проделали всю эту работу заранее и максимально упростили нашу итерацию? Если мы можем каким-то образом «очистить» нашу входную строку, чтобы она содержала только строчные буквы алфавита, мы могли бы избавить себя от необходимости проверять каждую итерацию, поскольку наш ввод уже был бы именно тем, что мы ожидали.

как нам это сделать? Один из способов - использовать так называемую таблицу ASCII.

Как определено в коде ASCII, ASCII означает американский стандартный код для обмена информацией. Это 7-битный код символа, в котором каждый бит представляет уникальный символ.

В приведенной ниже таблице показан код ASCII для первых 127 цифровых символов.

Для получения более полной таблицы ASCII посетите https://www.ascii-code.com/

Если мы более внимательно посмотрим на таблицу ASCII, мы увидим, что все наши строчные символы удобно сгруппированы вместе от 97 до 122. Мы можем использовать это в наших интересах и установить условие для фильтрации нашей строки, чтобы она содержала ТОЛЬКО код ASCII между 97 и 122 с помощью встроенного метода charCodeAt ().

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

  1. Превратите нашу строку в массив - ›установите для нее переменную с именем arr
  2. Отфильтруйте наш массив, чтобы он содержал только строчные буквы алфавита. Для этого мы будем использовать комбинацию filter, charCodeAt и ASCII.
  3. Инициализируйте два указателя, один из которых указывает на нулевой индекс и установлен в 0, а второй указывает на последний индекс. Мы будем называть это левым и правым соответственно.

Помните, что мы проверяем, работаем ли мы с палиндромом, поэтому нам нужно начать с начала и до конца и продвигаться внутрь.

4. Прокрутите наш только что отфильтрованный массив и проверьте, совпадают ли значения указателей. Если это так, переместите оба указателя к середине. В противном случае верните false

5. Верните истину в конце нашей функции. Если наша функция достигает конца, мы можем сделать вывод, что наш недавно отфильтрованный массив является палиндромом, поскольку мы завершили цикл

Решение

Мы заложили основу - давайте напишем код.

Глядя на наш псевдокод, наша первая пара шагов - превратить нашу входную строку в массив, а затем отфильтровать наш массив, чтобы он содержал только символы алфавита в нижнем регистре. Давай сделаем это сейчас:

Используя наш первый тестовый пример, мы видим, что, вызывая метод filter для нашего вновь созданного массива, мы можем фильтровать наши элементы по их ASCII-коду, вызывая charCodeAt () для наших элементов. Если их код ASCII находится между 97 и 122 (что означает, что они представляют собой символы нижнего регистра), мы сохраняем их в нашем newArray. Если нет, они удаляются.

Затем нам нужно будет инициализировать наши указатели, установив их в начале и в конце нашего массива.

Теперь нам нужно каким-то образом перебрать наш массив и заставить наши указатели перемещаться к середине массива, когда мы проверяем каждое значение на этом пути. В этом случае цикл while идеально подходит для наших нужд с условием, что он будет повторяться до тех пор, пока левый указатель не встретится с правым указателем.

Если наши значения совпадают, мы продолжим цикл. Если они этого не делают, мы можем сразу сказать, что палиндрома нет и выйти из цикла, вернуть ложное логическое значение.

Наше окончательное решение будет выглядеть следующим образом:

Заключение

Вот и все! То, что начиналось как довольно сложная проблема, оказалось довольно решаемым. Обрабатывая нашу входную строку сразу же и отфильтровывая наши нежелательные значения, мы можем избежать выполнения всей этой логики на каждой итерации и упростить нашу логическую проверку.

Понимание того, как работает ASCII, может стать мощным инструментом на вашем пути в качестве разработчика программного обеспечения. Помните об этом во время будущих упражнений по кодированию и / или технических собеседований - никогда не знаешь, когда это может пригодиться.

До скорого!

Источники

Код ASCII: Код ASCII - Расширенная таблица ASCII
https://www.ascii-code.com/