DEV Community

faangmaster
faangmaster

Posted on • Edited on

Проверка на палиндром, усложненная версия

Ссылка на leetcode: https://leetcode.com/problems/valid-palindrome/description/

Статья про проверку на палиндром: Проверка на палиндром.

Усложнение задачи проверки на палиндром.

Условие. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево. Нужно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: “A b a” -> палиндром, “A!23 * 32a”-> палиндром.

Решение. Для решения также будем использовать метод Two Pointers. Первый указатель будет указывать на начало строки, второй на конец строки. Будем итерироваться по строке до тех пока первый индекс меньше второго. На каждой итерации будем делать несколько проверок:

  1. Если символ, на который указывает первый указатель, не является буквой или цифрой, то игнорируем его увеличением индекса на единицу и переходим на следующую итерацию цикла.

  2. Если символ, на который указывает второй указатель, не является буквой или цифрой, то игнорируем его уменьшением индекса на единицу и переходим на следующую итерацию цикла.

  3. Если оба символа являются буквами или цифрами, то приводим их к одному реестру (например нижнему) и сравниваем. Если они не равны, то строка не палиндром. Если равны, то увеличиваем первый индекс и уменьшаем второй.

Time complexity: O(n), Space Complexity O(1).

Реализация:

    class Solution {
        public boolean isPalindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (!isAlphaNum(s.charAt(left))) {
                    left++;
                } else if (!isAlphaNum(s.charAt(right))) {
                    right--;
                } else {
                    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                        return false;
                    }
                    left++;
                    right--;
                }
            }
            return true;
        }

        //Можно заменить на Character.isLetterOrDigit()
        private boolean isAlphaNum(char c) {
            return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
        }
    }
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more