Вы, наверное, уже догадались, но сегодня мы поговорим о палиндромах! В частности, как мы проверяем палиндром? Третья часть моей серии блогов о структурах данных и алгоритмах для начинающих.

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

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

Для данной строки напишите функцию, которая проверяет, является ли строка палиндромом. Если строка является палиндромом, функция вернет true. Если это не палиндром, функция вернет false. Например, «racecar», «eye» и «madam» вернут true, а «apple», «water» и «window» - false.

Решение 1

В самом первом вопросе, который я затронул по поводу обращения строки, я представил три вспомогательных метода, которые упростили процесс обращения строки: разделение, обратное и объединение. Чтобы проверить наличие палиндрома, все, что нам нужно сделать, это убедиться, что слово написано именно так, как оно написано в обратном порядке! Для этого мы должны объявить переменную для присвоения строки с обратным написанием, а затем сравнить ее с исходной строкой. Приведенный ниже код будет очень похож на первый вопрос, только с одной дополнительной строкой для проверки строгого равенства. Я подробнее остановлюсь на тройном знаке равенства после решения.

В коде в строке 12 нет ничего нового. Я взял строку, разделил ее и, следовательно, преобразовал в массив, перевернул каждую букву в массиве и снова объединил ее, чтобы сформировать строку. В строке 13 я использую тройной знак равенства для проверки строгого равенства, что означает, что значения в backwardStr должны быть точно равны значениям в str. Есть несколько довольно явных различий между использованием знаков тройного и двойного равенства. Этот блог, написанный Брэндоном Морелли, очень хорошо это объясняет.

Давайте попробуем передать в эту функцию строку. Если мы передадим такое слово, как глаз, оно вернет истину. Однако, если мы передадим слово вроде «яблоко», это будет сравнение «elppa» и «яблоко», что вернет false. Это основы проверки палиндрома! Теперь давайте погрузимся в решение, требующее немного более сложной логики.

Решение 2

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

Начало начинается таким же образом, используя разделение строки для создания массива. Вспомогательный метод массива every принимает несколько параметров, но единственные два, которые нам нужны для этого вопроса, - это элемент, который передается каждый раз, а также индекс этого элемента. В решении они помечены как char для символа и i для индекса. Char представляет каждый символ, который передается на итерации, поэтому, если мы возьмем пример массива, [«r», «a», «c», «e», «c», «a», «r» ], на первой итерации массива char будет равно r. i представляет индекс символа, поэтому на первой итерации i будет равно 0. Помните, что индексы массива начинаются с 0. Array [0] равен r, array [1] равно a, array [2] равно c и т. д.

Замечательная часть помощника every заключается в том, что он возвращает логическое значение на основе определенного условия, которое передается. В строке 23 я указал условие, что если текущий символ, на котором мы находимся, равен к символу строки с индексом длины строки минус текущий индекс символа минус 1, затем мы возвращаем истину и переходим к следующему символу. Это было очень сложно, так что давайте разберемся с этим. Длина строки не начинается с 0, что отличается от индексации массива. Таким образом, длина строки racecar равна 7, а последний индекс ее символов - 6. Вот почему мы должны вычесть 1 из длины строки. Мы вычитаем текущий индекс символа из длины строки, чтобы уменьшить его в зависимости от того, насколько далеко в строке мы уже находимся. Например, если мы тестируем второй символ или массив с индексом 1, мы хотим настроить таргетинг и на второй символ, начиная с правого. Если созданный нами массив основан на строке «racecar» и мы тестируем a или второй символ слева, длина массива 7 минус 1 дает нам 6 минус индекс от 1 до даст нам 5. Массив [5] даст нам a, который является вторым символом справа.

Это объяснение могло сбить с толку, поэтому я настоятельно рекомендую, чтобы лучший способ познакомиться с индексацией массивов и навигацией - это практика! Откройте командную консоль Google, напишите строку, установите ее разделенную версию, равную переменной, и поиграйте с индексами!

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

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

На следующей неделе я займусь концепцией, а не вопросом. Я упомянул эту концепцию в первую неделю блога о структурах данных: временная и пространственная сложность, также известная как нотация Big O! Я объясню, что это такое, расскажу о различных типах, а затем рассмотрю предыдущие три вопроса и расскажу об их пространственно-временных сложностях. Это сложная тема для понимания, поэтому, если вам интересно, не стесняйтесь читать ее прямо сейчас!

Понравилась эта статья? Если да, то получите больше похожего контента, подписавшись на наш канал YouTube в Decoded!