{"id":128100,"date":"2022-09-14T18:44:06","date_gmt":"2022-09-14T18:44:06","guid":{"rendered":"https:\/\/blog.finxter.com\/?p=676729"},"modified":"2022-09-14T18:44:06","modified_gmt":"2022-09-14T18:44:06","slug":"how-to-find-all-palindromes-in-a-python-string","status":"publish","type":"post","link":"https:\/\/sickgaming.net\/blog\/2022\/09\/14\/how-to-find-all-palindromes-in-a-python-string\/","title":{"rendered":"How to Find All Palindromes in a Python String?"},"content":{"rendered":"\n
\n
\n
\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n
\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n
\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/div>\n
5\/5 – (1 vote) <\/div>\n<\/div>\n

Coding Challenge<\/h2>\n

\"\ud83d\udcac\" Challenge<\/strong>: Given a string. How to find all palindromes<\/a> in the string?<\/p>\n

For comprehensibility, allow me to quickly add a definition of the term palindrome:<\/p>\n

\"\ud83d\udca1\" Definition<\/strong>: A palindrome is a sequence of characters that reads the same backward as forward such as 'madam'<\/code>, 'anna'<\/code>, or '101'<\/code>.<\/p>\n

This article wants to give you a quick and easy solution in Python. First, we’ll solve the easier but important problem of checking if a substring is a palindrome in the first place:<\/p>\n

How to Check If String is Palindrome<\/h2>\n

You can easily check if a string is a palindrome by using the s<\/a>l<\/a>icing<\/a> expression word == word[::-1]<\/code> that evaluates to True<\/code> if the word is the same forward and backward, i.e., it is a palindrome.<\/p>\n

\"\ud83d\udc49\" Recommended Tutorial<\/strong>: Python Palindromes One-Liner<\/a><\/p>\n

Next, we’ll explore how to find all substrings in a Python string that are also palindromes. You can find our palindrome checker in the code solution (highlighted):<\/p>\n

Find All Substrings That Are Palindrome<\/h2>\n

The brute-force approach to finding all palindromes in a string is to iterate over all substrings in a nested for<\/a><\/code> loop. Then check each substring if it is a palindrome using word == word[::-1]<\/code>. Keep track of the found palindromes using the list.append()<\/a><\/code> method. Return the final list after traversing all substrings.<\/p>\n

Here’s the full solution:<\/p>\n

def find_palindromes(s): palindromes = [] n = len(s) for i in range(n): for j in range(i+1,n+1): word = s[i:j] if word == word[::-1]: palindromes.append(word) return palindromes print(find_palindromes('locoannamadam'))\n# ['l', 'o', 'oco', 'c', 'o', 'a', 'anna',\n# 'n', 'nn', 'n', 'a', 'ama', 'm', 'madam',\n# 'a', 'ada', 'd', 'a', 'm'] print(find_palindromes('anna'))\n# ['a', 'anna', 'n', 'nn', 'n', 'a'] print(find_palindromes('abc'))\n# ['a', 'b', 'c']<\/pre>\n
Runtime Complexity<\/h2>\n
This has cubic runtime complexity, i.e., for a string with length n<\/code>, we need to check O(n*n)<\/code> different words. Each word may have up to n<\/code> characters, thus the palindrome check itself is O(n)<\/code>. Together, this yields runtime complexity of O(n*n*n) = O(n\u00b3)<\/code>. <\/p>\n
Quadratic Runtime Solutions<\/h2>\n
Is this the best we can do? No! There’s also an O(n\u00b2) time solution!<\/p>\n
Here’s a quadratic-runtime solution to find all palindromes in a given string that ignores the trivial one-character palindromes (significantly modified from source<\/a>):<\/p>\n
def find_palindromes(s, j, k): ''' Finds palindromes in substring between indices j and k''' palindromes = [] while j >= 0 and k < len(s): if s[j] != s[k]: break palindromes.append(s[j: k + 1]) j -= 1 k += 1 return palindromes def find_all(s): '''Finds all palindromes (non-trivial) in string s''' palindromes = [] for i in range(0, len(s)): palindromes.extend(find_palindromes(s, i-1, i+1)) palindromes.extend(find_palindromes(s, i, i+1)) return palindromes print(find_all('locoannamadam'))\n# ['oco', 'nn', 'anna', 'ama', 'ada', 'madam'] print(find_all('anna'))\n# ['nn', 'anna'] print(find_all('abc'))\n# []\n<\/pre>\n
Feel free to join our community of ambitious learners like you (we have cheat sheets too): \"\u2764\"<\/p>\n","protected":false},"excerpt":{"rendered":"
5\/5 – (1 vote) Coding Challenge Challenge: Given a string. How to find all palindromes in the string? For comprehensibility, allow me to quickly add a definition of the term palindrome: Definition: A palindrome is a sequence of characters that reads the same backward as forward such as ‘madam’, ‘anna’, or ‘101’. This article wants […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[857],"tags":[73,468,528],"class_list":["post-128100","post","type-post","status-publish","format-standard","hentry","category-python-tut","tag-programming","tag-python","tag-tutorial"],"_links":{"self":[{"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/posts\/128100","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/comments?post=128100"}],"version-history":[{"count":0,"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/posts\/128100\/revisions"}],"wp:attachment":[{"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/media?parent=128100"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/categories?post=128100"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sickgaming.net\/blog\/wp-json\/wp\/v2\/tags?post=128100"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}