Friday, September 29, 2023
HomePythonMethods to Discover All Palindromes in a Python String? – Finxter

# Methods to Discover All Palindromes in a Python String? – Finxter

## Coding Problem

💬 Problem: Given a string. Methods to discover all palindromes within the string?

For comprehensibility, permit me to rapidly add a definition of the time period palindrome:

💡 Definition: A palindrome is a sequence of characters that reads the identical backward as ahead akin to `'madam'`, `'anna'`, or `'101'`.

This text desires to present you a fast and straightforward answer in Python. First, we’ll clear up the simpler however essential drawback of checking if a substring is a palindrome within the first place:

## Methods to Examine If String is Palindrome

You possibly can simply test if a string is a palindrome through the use of the slicing expression `phrase == phrase[::-1]` that evaluates to `True` if the phrase is identical ahead and backward, i.e., it’s a palindrome.

👉 Really useful Tutorial: Python Palindromes One-Liner

Subsequent, we’ll discover easy methods to discover all substrings in a Python string which might be additionally palindromes. Yow will discover our palindrome checker within the code answer (highlighted):

## Discover All Substrings That Are Palindrome

The brute-force method to discovering all palindromes in a string is to iterate over all substrings in a nested `for` loop. Then test every substring if it’s a palindrome utilizing `phrase == phrase[::-1]`. Hold monitor of the discovered palindromes utilizing the `record.append()` technique. Return the ultimate record after traversing all substrings.

```def find_palindromes(s):
palindromes = []
n = len(s)
for i in vary(n):
for j in vary(i+1,n+1):
phrase = s[i:j]
if phrase == phrase[::-1]:
palindromes.append(phrase)
return palindromes

# ['l', 'o', 'oco', 'c', 'o', 'a', 'anna',
#  'n', 'nn', 'n', 'a', 'ama', 'm', 'madam',
#  'a', 'ada', 'd', 'a', 'm']

print(find_palindromes('anna'))
# ['a', 'anna', 'n', 'nn', 'n', 'a']

print(find_palindromes('abc'))
# ['a', 'b', 'c']```

## Runtime Complexity

This has cubic runtime complexity, i.e., for a string with size `n`, we have to test `O(n*n)` completely different phrases. Every phrase could have as much as `n` characters, thus the palindrome test itself is `O(n)`. Collectively, this yields runtime complexity of `O(n*n*n) = O(n³)`.

Is that this the perfect we will do? No! There’s additionally an O(n²) time answer!

Right here’s a quadratic-runtime answer to search out all palindromes in a given string that ignores the trivial one-character palindromes (considerably modified from supply):

```def find_palindromes(s, j, okay):
''' Finds palindromes in substring between indices j and okay'''
palindromes = []
whereas j >= 0 and okay < len(s):
if s[j] != s[k]:
break
palindromes.append(s[j: k + 1])
j -= 1
okay += 1
return palindromes

def find_all(s):
'''Finds all palindromes (non-trivial) in string s'''
palindromes = []
for i in vary(0, len(s)):
palindromes.lengthen(find_palindromes(s, i-1, i+1))
palindromes.lengthen(find_palindromes(s, i, i+1))
return palindromes

print(find_all('anna'))
# ['nn', 'anna']

print(find_all('abc'))
# []
```

Be happy to hitch our neighborhood of bold learners such as you (now we have cheat sheets too): ❤️

RELATED ARTICLES