Saturday, October 1, 2022
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.

Right here’s the total answer:

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


print(find_palindromes('locoannamadam'))
# ['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³).

Quadratic Runtime Options

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('locoannamadam'))
# ['oco', 'nn', 'anna', 'ama', 'ada', 'madam']

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments