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

I’m trying to check for a palindrome with Python. The code I have is very for-loop intensive.

And it seems to me the biggest mistake people do when going from C to Python is trying to implement C logic using Python, which makes things run slowly, and it’s just not making the most of the language.

I see on this website. Search for “C-style for”, that Python doesn’t have C-style for loops. Might be outdated, but I interpret it to mean Python has its own methods for this.

I’ve tried looking around, I can’t find much up to date (Python 3) advice for this. How can I solve a palindrome challenge in Python, without using the for loop?

I’ve done this in C in class, but I want to do it in Python, on a personal basis. The problem is from the Euler Project, great site By the way,.

def isPalindrome(n):
    lst = [int(n) for n in str(n)]
    l=len(lst)
    if l==0 || l==1:
        return True
    elif len(lst)%2==0:
        for k in range (l)
        #####
    else:
        while (k<=((l-1)/2)):
            if (list[]):
                #####   

for i in range (999, 100, -1):
    for j in range (999,100, -1):
        if isPalindrome(i*j):
            print(i*j)
            break

I’m missing a lot of code here. The five hashes are just reminders for myself.

Concrete questions:

1. In C, I would make a for loop comparing index 0 to index max, and then index 0+1 with max-1, until something something. How to best do this in Python?

2. My for loop (in in range (999, 100, -1), is this a bad way to do it in Python?

3. Does anybody have any good advice, or good websites, or resources for people in my position? I’m not a programmer, I don’t aspire to be one, I just want to learn enough so that when I write my bachelor’s degree thesis (electrical engineering), I don’t have to simultaneously LEARN an applicable programming language while trying to obtain good results in the project. “How to go from basic C to great application of Python”, that sort of thing.

4. Any specific bits of code to make a great solution to this problem would also be appreciated, I need to learn good algorithms.. I am envisioning 3 situations. If the value is zero or single digit, if it is of odd length, and if it is of even length. I was planning to write for loops…

PS: The problem is: Find the highest value product of two 3 digit integers that is also a palindrome.

Given a string, write a python function to check if it is palindrome or not. A string is said to be a palindrome if the reverse of the string is the same as the string. For example, “radar” is a palindrome, but “radix” is not a palindrome.

Examples: 

Input : malayalam
Output : Yes

Input : geeks
Output : No

Method #1 

1. Find reverse of the string
2. Check if reverse and original are same or not.

Time complexity: O(n)
Auxiliary Space: O(1)

Iterative Method: This method is contributed by Shariq Raza. Run a loop from starting to length/2 and check the first character to the last character of the string and second to second last one and so on …. If any character mismatches, the string wouldn’t be a palindrome.

Below is the implementation of above approach: 

Time complexity: O(n)
Auxiliary Space: O(1)

Method using the inbuilt function to reverse a string: 
In this method, the predefined function ‘ ‘.join(reversed(string)) is used to reverse string. 

Below is the implementation of the above approach: 

Time complexity: O(n)
Auxiliary Space: O(n)

Method using one extra variable: In this method, the user takes a character of string one by one and store it in an empty variable. After storing all the characters user will compare both the string and check whether it is palindrome or not. 

Time complexity: O(n)
Auxiliary Space: O(n)

Method using flag: In this method, the user compares each character from starting and ending in a for loop and if the character does not match then it will change the status of the flag. Then it will check the status of the flag and accordingly and print whether it is a palindrome or not.  

Time complexity: O(n)
Auxiliary Space: O(1)

Method using recursion: 
This method compares the first and the last element of the string and gives the rest of the substring to a recursive call to itself. 

Time complexity: O(n)
Auxiliary Space: O(n)

Method : Using extend() and reverse() methods

Time complexity: O(n) where n is the length of a given string
Auxiliary space: O(n)

This article is contributed by Sahil Rajput. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Last Updated :
16 Feb, 2023

Like Article

Save Article

In this tutorial, you’ll learn how to use Python to check if a string is a palindrome. You’ll learn six different ways to check if a string is a palindrome, including using string indexing, for loops, the reversed() function.

You’ll also learn the limitations of the different approaches, and when one might be better to use than another. But before we dive in, let’s answer a quick question:

The Quick Answer: Use String Indexing

String indexing provides the simplest way in Python to check if a string is a palindrome. String indexing can be used to iterate over a string in reverse order.

One of the greatest things about Python indexing is that you can set a step counter as well, meaning you can move over an iterable at the desired rate. The way that we’ll make use of this is to use a step of -1, meaning that we move over the iterable from the back to the front.

An important thing to keep in mind is that your string may have different casing as well as spaces. Because of this, we’ll need to preprocess our string to remove capitalization and any spaces.

Let’s take a look at using string indexing to check if a string is a palindrome in Python:

# Use String Indexing in Python to check if a String is a Palindrome

a_string = 'Was it a car or a cat I saw'

def palindrome(a_string):
    a_string = a_string.lower().replace(' ', '')
    return a_string == a_string[::-1]

print(palindrome(a_string))

# Returns: True

Let’s explore what we’ve done in the code above:

1. We define a function, palindrome(), that takes a single string as its only parameter
2. We then re-assign the string to itself but lower all the character cases (using the .lower() method) and remove any spaces (using the .replace() method)
3. We then evaluate whether or not the modified string is equal to the modified string in reverse order
4. This returns True if the string is a palindrome, and False if it is not

Now, let’s take a look at how we can use the Python reversed() function to check if a string is a palindrome.

Use the Python Reversed Function to Check if a String is a Palindrome

Python comes with a built-in function, reversed(), which reverses an iterable item, such as a string. You can pass in some iterable item, be it a string, a list, or anything else ordered, and the function returns the reversed version of it.

Let’s take a look at how we can use the reversed() function:

# Use the Reversed() function in Python to check if a String is a Palindrome

a_string = 'Was it a car or a cat I saw'

def palindrome(a_string):
    a_string = a_string.lower().replace(' ', '')
    reversed_string = ''.join(reversed(a_string))
    return a_string == reversed_string

print(palindrome(a_string))

# Returns: True

Let’s take a look at what our function does:

1. Similar to the method above, the function first changes all casing to lower case and removes all spaces
2. Then, it uses the reverse() function to reverse the string.
3. Because the reverse() function returns a reversed object, we need to turn it back into a string. This can be done using the .join() method.
4. Finally, the two strings are evaluated against whether or not they’re equal.

In the next section, you’ll learn how to use a for loop to check if a string is a palindrome.

Using a For Loop to Check if a Python String is a Palindrome

You can also use a Python for-loop to loop over a string in reverse order, to see if a string is a palindrome or not.

Let’s see how we can use a for loop to check if a string is a palindrome:

# Use a For Loop in Python to check if a String is a Palindrome

a_string = 'Was it a car or a cat I saw'

def palindrome(a_string):
    a_string = a_string.lower().replace(' ', '')
    reversed_string = ''
    for i in range(len(a_string), 0, -1):
        reversed_string += a_string[i-1]
    return a_string == reversed_string

print(palindrome(a_string))

# Returns: True

What we’ve done here is traversed the list from the last index, -1, to its first, 0. We then assign that value to a string reversed. Finally, we evaluate whether the two strings are equal.

In the next section, you’ll learn how to use a Python while loop to see if a palindrome exists.

Using a Python While Loop to Check if a String is a Palindrome

In this section, let’s explore how to use a Python while loop to see if a string is a palindrome or not.

One of the benefits of this approach is that we don’t actually need to reassign a reversed string, which, if your strings are large, won’t consume much memory.

Let’s see how we can use a Python while loop:

# Use a While Loop in Python to check if a String is a Palindrome

a_string = 'Was it a car or a cat I saw'

def palindrome(a_string):
    a_string = a_string.lower().replace(' ', '')
    first, last = 0, len(a_string) - 1

    while(first < last):
        if(a_string[first] == a_string[last]):
            first += 1
            last -= 1
        else:
            return False

    return True

print(palindrome(a_string))

# Returns: True

Let’s break down what the code block above is doing:

1. We define a function, palindrome(), which accepts a string as its only argument
2. We format our string in all lowercase and replace any spaces
3. We then create two variables, first and last which are equal to 0 and the length of the list minus 1, respectively
4. We then create a while loop, which runs as long as the value of first is less than last
5. The loop evaluates if the indexed value of first and last are equal to one another
6. If they are, the values are incremented and decremented by 1, respectively
7. If not, the function returns False

A major performance benefit here can be that if a string is clearly not a palindrome, say if the first and last characters don’t match, then the loop breaks. This saves us significant memory and time.

Check if a String is a Palindrome Using Recursion in Python

In this section, you’ll learn how to use recursion to check if a string is a palindrome in Python. Recursive functions can be used to make your code simpler and cleaner while providing extensive functionality.

Let’s take a look at how we can develop a recursive function that checks whether or not a string is a palindrome:

# Using Recursion to Check if a String is a Palindrome in Python
a_string = 'Was it a car or a cat I saw'

def palindrome(a_string):
    a_string = a_string.lower().replace(' ', '')
    if a_string[0] != a_string[-1]:
        return False
    else:
        return palindrome(a_string[1:-1])


print(palindrome(a_string))

# Returns:
# True

Let’s break down what we did in the code above:

1. We defined a function, palindrome(), which takes a string as its only parameter
2. The function first lowercases the string and removes any spaces
3. Then, it checks if the first and last characters are the same
4. If they are not, then the function returns False
5. If they are, the function is called recursively, ignoring the first and last letters

In the next section, you’ll learn how to check whether or not a number is a palindrome.

Check if a Number is a Palindrome in Python

The easiest way to check if a number is a Python palindrome is to convert the number to a string and apply any of the methods mentioned above.

Let’s see how we can do this using the string indexing method:

# Use String Indexing in Python to check if a Number is a Palindrome

a_number = 123454321

def palindrome(number):
    number = str(number)
    return number == number[::-1]

print(palindrome(a_number))

# Returns: True

In order to check if a number is a palindrome in Python, we converted the number to a string using the str() method. From there, we can simply check if the resulting string is a palindrome using any of the methods above. In the code example, we used string indexing to reverse the string.

What is the Fastest Way to Check if a String is a Palindrome in Python?

In the code above, you learned six different ways to use Python to check if a string is a palindrome. At this point, you may be wondering what method to use. In many cases, you’ll want to strive for readability and speed.

In this section, we tested the speed of the different methods using a palindrome that is over ten million characters long. Because recursion is generally capped at 1,000 recursive calls, this method is not tested.

Below, you’ll find the results of the tests:

The image below breaks down the speed comparison:

Conclusion

In this post, you learned a number of different ways to check if a Python string is a palindrome. You learned how to do this with Python string indexing, the Python reversed() function, both for and while loops. You also learned how to check if a number is a Python palindrome and how to search a larger string for a substring that is a palindrome.

Additional Documentation

To learn more about related topics, check out the tutorials below:

• Python String Contains: Check if a String Contains a Substring
• How to Check if a String is Empty in Python
• How to Concatenate Strings in Python: A Complete Guide
• Python: Count Words in a String or File
• To learn more about the reversed() function, check out the official documentation here.

Автор оригинала: 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. Я надеюсь, что вы попробуете каждое решение.