Как найти слова палиндромы

Содержание

1. Что такое палиндром
2. Проверка слова
3. Проверка фразы

Давайте реализуем алгоритм поиска слов-палиндромов на Java.

Для начала надо определиться, что же такое палиндром? Палиндром – это слово или строка текста, которая читается слева направо и справа налево одинаково. Например, палиндромами являются такие слова как «ага», «дед», «довод», «кабак», «мадам», «шалаш». В более широком смысле число «101» также является палиндромом.

Давайте сначала рассмотрим более простой алгоритм, который на вход получает одно слово без пробелов. В случае, если данное слово палиндром – возвращаем true.

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

private boolean isWordPalindrome(String word) {
    var chars = word.toCharArray();
    var left = 0; // индекс первого символа
    var right = chars.length – 1; // индекс последнего символа
    while (left < right) { // пока не дошли до середины слова
        if (chars[left] != chars[right]) {
            return false;
        }
        left++;
        right–;
    }
    return true;
}

Сначала преобразуем с помощью метода toCharArray() исходную строку в массив символов, чтобы можно было обращаться к каждому отдельному символу по его порядковому индексу.

Затем заводим две переменных left и right для хранения левого и правого индекса соответственно.

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

В самом цикле проверяем равенство левого и правого символа. Если они различны – сразу возвращаем false и выходим из метода. Далее левый символ увеличиваем на 1, а правый – уменьшаем на 1.

Если мы дошли до середины строки и ни разу не встретили различий, то возвращаем true.

Теперь усложним задачу и будем проверять не отдельное слово, а целую фразу. Приведу несколько фраз-палиндромов. Попробуйте прочитать их справа налево.

• Искать такси
• Лидер бредил
• А роза упала на лапу Азора
• Уж редко рукою окурок держу

Как видите, тут уже встречаются пробелы, которые мы просто должны игнорировать. Также нам нужно сравнивать символы независимо от регистра.

Взяв за основу ранее рассмотренный метод, немного модифицируем его, преобразуя сначала все символы в нижний регистр:

private boolean isTextPalindrome(String text) {
    var chars = text.toLowerCase().toCharArray();
    var left = 0;
    var right = chars.length – 1;
    while (left < right) {
        if (chars[left] != chars[right]) {
            return false;
        }
        // …

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

do {
    left++;
} while (left < right && chars[left] == ‘ ‘);

Аналогично правый индекс уменьшаем до тех пор, пока он больше левого и пока правый символ – пробел:

do {
    right–;
} while (right > left && chars[right] == ‘ ‘);

В итоге наш улучшенный метод примет следующий вид:

Помимо пробелов во фразах могут встречаться и другие символы. Например, знаки препинания. В таком случае, просто замените явную проверку на пробел на вызов метода Character.isLetterOrDigit().

Реализацию данного алгоритма у вас могут спросить на собеседовании, поэтому его полезно знать.

Автор оригинала: Team Python Pool.

Один из самых простых и часто задаваемых вопросов на интервью – проверить, является ли строка палиндромом или нет, используя Python.

Палиндром – это строка или число, которое, если повернуть вспять, равно исходному значению. Например, если мы перевернем строку MALAYALAM, мы получим обратно исходную строку. Кроме того, если мы перевернем число 12321, мы получим 12321 обратно. Они известны как палиндромы.

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

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

1. Проверьте Палиндром с помощью нарезки (slicing) в Python
2. Проверьте Палиндром с помощью функции reversed() В Python
3. Проверьте Палиндром с помощью цикла while в Python
4. Проверка того, является ли число палиндромом в Python с помощью цикла
5. Проверка того, является ли фраза палиндромом в Python
6. Как найти самую длинную палиндромную подстроку в строке

1. Проверьте Palindrome с помощью нарезки в Python

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

def check_palindrome(string):
    # transversing the string from last to first
    reversed_string = string[::-1]
        if string == reversed_string:
            print(string, "is a palindrome")
        else:
            print(string, "is not a Palindrome")
    
if name=='main':
    check_palindrome("RADAR")
    check_palindrome("PythonPool")

Output-
RADAR is a palindrome
PythonPool is not a Palindrome

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

2. Проверьте Палиндром с помощью цикла в Python

def is_palindrome(string):
    reversed_string = ""
    # transversing through string from last
    for i in range(len(string), 0, -1):
        # Addind last characters of string into a new string
        reversed_string += string[i-1]
        if string == reversed_string:
            print("Palindrome")
        else:
            print("Not a palindrome")
            
if __name__ == __'main'__:
    is_palindrome("racecar")
    is_palindrome("Python")

Output-
Palindrome
Not a palindrome

3. Проверьте Палиндром С Помощью функции reversed() в Python

string="MALAYALAM"
# joining characters of reversed string one by one
reversed_string = ''.join(reversed(string))
    if reversed_string == string:
        print(string," is Palindrome")
    else:
        print(string,"Not a Palindrome")

Output-
MALAYALAM is Palindrome

4. Проверьте на Палиндром с помощью цикла while в Python

def check_palindrome(string):
    l = len(string)
    first = 0
    last = l - 1
    isPalindrome = True
    
    # ensuring that we do not iterate through more than half                          #   of the list
    while first < last:
        # if the first character is same as last character keep     #       moving further
        if string[first] == string[last]:
            first = first + 1
            last = last - 1
     # if the characters at first and last do not match break #      the loop
     else:
        isPalindrome = False
        break
        
    return isPalindrome


if __name__ == __'main'__:
    isPalindrome = check_palindrome("MADAM")

    if isPalindrome:
        print("It is a palindrome ")
    else:
        print("Not a Palindrome")

Output-
It is a palindrome

5. Проверка является ли число Палиндромом в Python с помощью цикла

Мы будем использовать следующую концепцию:
Число = 12321
Остаток этого числа, деленный на 10, равен:
Число% 10 = 12321% 10 = 1
Reverse_Number=Remainder=1
Затем мы разделим число на 10.
Число = Number/10 = 12321//10 = 1232
Остаток = 1232% 10 = 2
Reverse_Number=Remainder=12
Число = 1232/10 = 123
Остаток = 123% 10 = 3
Reverse_Number=Remainder=123
Число = 123/10 = 12
Остаток = 12% 10 = 2
Reverse_Number=Remainder=1232
Число = 12/10 = 1
Остаток = 1% 10 = 1
Reverse_Number=Remainder=12321

Программа:

number = 12321
reverse_number = 0
n = number

# while we have not reached the end of the number
while n != 0:
    # finding the last element of number 'n'
    rem = n % 10
    reverse_number = reverse_number * 10 + rem
    n = int(n / 10)
    
if number == reverse_number:
    print("Palindrome")
else:
    print("Not a Palindrome")

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

number = 12321

# converting the number to string and then reversing it
if str(number)[::-1] == str(number):
    print("Number:", number, " is a Palindrome")
else:
    print("Number:", number, " is not a Palindrome")

Output-
Number: 12321 is a Palindrome

6. Проверка того, является ли фраза палиндромом в Python

Проверка, является ли фраза палиндромом или нет, отличается от проверки, является ли слово палиндромом или нет.
Например, фраза “Too hot to hoot” является палиндромом, если игнорировать верхний регистр – нижний регистр и пробелы в символах.

def is_palindrome(string):
    reversed_string = ""
    # Removing all the spaces
    s = string.replace(" ","")
    # making the whole string in lowercase characters 
    s = s.lower()
    for i in range(len(s), 0, -1):
        if s[i-1] >= 'a' and s[i-1] <= 'z':
            reversed_string += s[i - 1]
    if s == reversed_string:
        print("Palindrome")
    else:
        print("Not a palindrome")
        

if __name__ == '__main__':
    is_palindrome("Too hot to hoot")
    is_palindrome("Python")

Output-
Palindrome
Not a palindrome

Есть и другие типы палиндромов, например: “Is it crazy how saying sentences backward creates backward sentences saying how crazy it is”. Он отличается от других палиндромов, которые мы обсуждали до сих пор, потому что здесь, если мы перевернем символы, это не палиндром. Но если мы перевернем его слово за словом, то это будет палиндром.

Программа:

string = 'Is it crazy how saying sentences backwards creates backwards sentences saying how crazy it is'
string1 = string.lower()
string1 = string.replace(" ", "")
new_string = ""

# Wherever there is any space make a list element
list1 = string1.split(" ")

# join the list into string starting from the last
reverse = "".join(list1[::-1])
reverse_string = ""

for i in reverse:
    # adding only characters in the new string
    if i >= 'a' and i <= 'z': 
        reverse_string+=i 

for i in string1:
    if i >= 'a' and i <= 'z':
        new_string += i

if new_string == reverse_string:
    print(string, ":Palindrome")
else:
    print(string, ":Not a Palindrome")

Output-
Is it crazy how saying sentences backward creates backward sentences saying how crazy it is: Palindrome

7. Как найти самую длинную палиндромную подстроку в строке

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

m = ""
s = 'babad'

for i in range(len(s)):
    # iterating through the string from the last
    for j in range(len(s), i, -1):
    # ensuring that we do not iterate through more than half of 
    # the string
        if len(m) >= j-i:
            break
        elif s[i:j] == s[i:j][::-1]:
            m = s[i:j]

print(m)

Алгоритмическая сложность для приведенной выше программы равна O(n^2), так как у нас есть цикл for внутри другого цикла for.

Читайте также:

• Как преобразовать строку в нижний регистр
• Как вычислить Квадратный корень
• Пользовательский ввод | Функция input() | Ввод с клавиатуры

Вывод

Мы изучили, что такое палиндром, как проверить, является ли строка или число палиндромом. Мы также рассмотрели некоторые распространенные вопросы интервью, такие как проверка фразы, если она является палиндромом, и поиск самой длинной подстроки, которая является палиндромом в Python. Я надеюсь, что вы попробуете каждое решение.

Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное. 

Условия

В переменной X лежит какое-то целое число

Задача — проверить, является ли это число палиндромом.

Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.

Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:

121 — это палиндром.

А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).

12321 — и это палиндром.

Решение, где используем строки

Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.

Сначала решим это на Python. Тут вообще суть в одной строке:

X = 121
if str(X) == str(X)[::-1]:
    print("Это палиндром")
else:
    print("Это не палиндром")

Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:

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

Теперь решим это же, но на JavaScript:

var X = 121;
if (X.toString().split("").reverse().join("") == X.toString()) {
    console.log("Это палиндром")
} else {
    console.log("Это не палиндром")
}

Здесь мы использовали другой метод пересборки:

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

function palindrome(x) {
}

Теперь обработаем три стандартные ситуации:

Запишем это на JavaScript:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
}

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

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
    // сюда будем собирать число в обратном порядке
    temp = 0;
    // а тут будем хранить промежуточные значения икса
    preX = x;
    // пока не дойдём до середины числа — повторяем цикл
    while (x > temp) {
        // берём самую правую цифру в числе — это остаток от деления на 10
        pop = x%10;
        // запоминаем старое значение переменной X
        preX = x;
        // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10
        x /= 10;
        // добавляем отрезанную цифру к обратной переменной
        temp = temp*10 + pop;
    }
    // если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром
    // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам
    if(x == temp || preX == temp)
        return true;
    // 
    else
        return false;
};

Для запуска кода просто вызываем функцию и передаём её нашу переменную:

// запускаем код
var X = 121;
console.log(palindrome(X));

Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.