[Tut] How to Find All Palindromes in a Python String?

How to Find All Palindromes in a Python String?

<div>
<div class="kk-star-ratings kksr-auto kksr-align-left kksr-valign-top" data-payload="{&quot;align&quot;:&quot;left&quot;,&quot;id&quot;:&quot;676729&quot;,&quot;slug&quot;:&quot;default&quot;,&quot;valign&quot;:&quot;top&quot;,&quot;ignore&quot;:&quot;&quot;,&quot;reference&quot;:&quot;auto&quot;,&quot;class&quot;:&quot;&quot;,&quot;count&quot;:&quot;1&quot;,&quot;readonly&quot;:&quot;&quot;,&quot;score&quot;:&quot;5&quot;,&quot;best&quot;:&quot;5&quot;,&quot;gap&quot;:&quot;5&quot;,&quot;greet&quot;:&quot;Rate this post&quot;,&quot;legend&quot;:&quot;5\/5 - (1 vote)&quot;,&quot;size&quot;:&quot;24&quot;,&quot;width&quot;:&quot;142.5&quot;,&quot;_legend&quot;:&quot;{score}\/{best} - ({count} {votes})&quot;,&quot;font_factor&quot;:&quot;1.25&quot;}">
<div class="kksr-stars">
<div class="kksr-stars-inactive">
<div class="kksr-star" data-star="1" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="2" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="3" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="4" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="5" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
</p></div>
<div class="kksr-stars-active" style="width: 142.5px;">
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
</p></div>
</div>
<div class="kksr-legend" style="font-size: 19.2px;"> 5/5 – (1 vote) </div>
</div>
<h2>Coding Challenge</h2>
<p class="has-base-background-color has-background"><img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f4ac.png" alt="?" class="wp-smiley" style="height: 1em; max-height: 1em;" /> <strong>Challenge</strong>: Given a string. How to find all <a rel="noreferrer noopener" href="https://blog.finxter.com/palindromes-in-one-line-python/" data-type="post" data-id="3613" target="_blank">palindromes</a> in the string?</p>
<p>For comprehensibility, allow me to quickly add a definition of the term palindrome:</p>
<p class="has-global-color-8-background-color has-background"><img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f4a1.png" alt="?" class="wp-smiley" style="height: 1em; max-height: 1em;" /> <strong>Definition</strong>: A palindrome is a sequence of characters that reads the same backward as forward such as <code>'madam'</code>, <code>'anna'</code>, or <code>'101'</code>.</p>
<p>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>
<h2>How to Check If String is Palindrome</h2>
<p>You can easily check if a string is a palindrome by using the <a href="https://blog.finxter.com/introduction-to-slicing-in-python/" data-type="post" data-id="731">s</a><a rel="noreferrer noopener" href="https://blog.finxter.com/introduction-to-slicing-in-python/" data-type="post" data-id="731" target="_blank">l</a><a href="https://blog.finxter.com/introduction-to-slicing-in-python/" data-type="post" data-id="731">icing</a> expression <code>word == word[::-1]</code> that evaluates to <code>True</code> if the word is the same forward and backward, i.e., it is a palindrome.</p>
<p class="has-base-background-color has-background"><img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f449.png" alt="?" class="wp-smiley" style="height: 1em; max-height: 1em;" /> <strong>Recommended Tutorial</strong>: <a href="https://blog.finxter.com/palindromes-in-one-line-python/" data-type="post" data-id="3613" target="_blank" rel="noreferrer noopener">Python Palindromes One-Liner</a></p>
<p>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>
<h2>Find All Substrings That Are Palindrome</h2>
<p class="has-global-color-8-background-color has-background">The brute-force approach to finding all palindromes in a string is to iterate over all substrings in a nested <code><a rel="noreferrer noopener" href="https://blog.finxter.com/python-loops/" data-type="post" data-id="4596" target="_blank">for</a></code> loop. Then check each substring if it is a palindrome using <code>word == word[::-1]</code>. Keep track of the found palindromes using the <code><a href="https://blog.finxter.com/python-list-append/" data-type="post" data-id="6605" target="_blank" rel="noreferrer noopener">list.append()</a></code> method. Return the final list after traversing all substrings.</p>
<p>Here’s the full solution:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="7" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">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'))
# ['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']</pre>
<h2>Runtime Complexity</h2>
<p>This has cubic runtime complexity, i.e., for a string with length <code>n</code>, we need to check <code>O(n*n)</code> different words. Each word may have up to <code>n</code> characters, thus the palindrome check itself is <code>O(n)</code>. Together, this yields runtime complexity of <code>O(n*n*n) = O(n³)</code>. </p>
<h2>Quadratic Runtime Solutions</h2>
<p>Is this the best we can do? No! There’s also an O(n²) time solution!</p>
<p>Here’s a quadratic-runtime solution to find all palindromes in a given string that ignores the trivial one-character palindromes (significantly modified from <a rel="noreferrer noopener" href="https://www.educative.io/m/find-all-palindrome-substrings" data-type="URL" data-id="https://www.educative.io/m/find-all-palindrome-substrings" target="_blank">source</a>):</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">def find_palindromes(s, j, k): ''' Finds palindromes in substring between indices j and k''' palindromes = [] while j >= 0 and k &lt; 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'))
# ['oco', 'nn', 'anna', 'ama', 'ada', 'madam'] print(find_all('anna'))
# ['nn', 'anna'] print(find_all('abc'))
# []
</pre>
<p>Feel free to join our community of ambitious learners like you (we have cheat sheets too): <img src="https://s.w.org/images/core/emoji/14.0.0/72x72/2764.png" alt="❤" class="wp-smiley" style="height: 1em; max-height: 1em;" /></p>
</div>


https://www.sickgaming.net/blog/2022/09/...on-string/