![]() |
|
[Tut] How to Find All Palindromes in a Python String? - Printable Version +- Sick Gaming (https://sickgaming.net) +-- Forum: Programming (https://sickgaming.net/forum-76.html) +--- Forum: Python (https://sickgaming.net/forum-83.html) +--- Thread: [Tut] How to Find All Palindromes in a Python String? (/thread-99954.html) |
[Tut] How to Find All Palindromes in a Python String? - xSicKxBot - 09-16-2022 How to Find All Palindromes in a Python String? 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 Code: 'madam'Code: 'anna'Code: '101'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: How to Check If String is Palindrome You can easily check if a string is a palindrome by using the slicing expression Code: word == word[::-1]Code: True Recommended Tutorial: Python Palindromes One-LinerNext, 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): Find All Substrings That Are Palindrome The brute-force approach to finding all palindromes in a string is to iterate over all substrings in a nested Code: forCode: word == word[::-1]Code: list.append()Here’s the full solution: Code: 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']This has cubic runtime complexity, i.e., for a string with length Code: nCode: O(n*n)Code: nCode: O(n)Code: O(n*n*n) = O(n³)Quadratic Runtime Solutions Is this the best we can do? No! There’s also an O(n²) time solution! 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): Code: 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'))
# ['oco', 'nn', 'anna', 'ama', 'ada', 'madam'] print(find_all('anna'))
# ['nn', 'anna'] print(find_all('abc'))
# []Feel free to join our community of ambitious learners like you (we have cheat sheets too):
|