A palindrome is a number, word, or sentence that reads the same backward as forward, for instance, “Mom”. In the computer science domain, palindrome plays an important role while working with any programming language. Often companies like Amazon, Facebook, and Microsoft test the conceptual knowledge of candidates by involving the competitive question as a part of the technical interview.
A valid palindrome is one such competitive problem that you should absolutely understand in order to crack a job in your dream company. In this article, we will study the palindrome problem and different approaches to solve it using python code and output. Let’s get started!
What is a Valid Palindrome Problem?
Given the string ‘s’, print ‘true’ if it is a palindrome, or ‘false’ otherwise.
For instance, "Was it a car or a cat I saw"
The above sentence reads the same backward as forward. You can solve this problem using different approaches. Let’s dive deep to understand these approaches in detail below.
How to Check Valid Palindrome?
Below are three approaches by which you can solve the valid palindrome problem.
1) Using the traditional approach
The first solution that comes to your mind while solving a valid palindrome problem is by using an iterative approach. In this method, you run a loop from the starting of the string till half of its length and repeatedly check the first character with the last character, the second with the second last, and so on. If any character does not match, the string will not be a palindrome.
Python program using an iterative approach
The time complexity of the solution using this problem is O(n/2) where n is the number of characters in the string. It is because we run the loop in the string till n/2 characters and compare it in reverse order.
2) Using Library Function
This approach is the most basic method to check whether the sentence is palindrome or not by reversing the original string and comparing it. To reverse the given string using the slicing method in a string library function. The slicing method helps to carve out the substring from the original string using the bracket notation that specifies the start and the end index of the substring. Also, remember to eliminate the non-alphanumeric number using the slicing method on the original string. Later, compare the original string with the reversed string and return true if they match or false otherwise.
Python code using library function
The time complexity of the solution using this approach is O(n) where n is the total number of characters in the string. It is because we traverse through the original string only once. Similarly, the space complexity of the problem is O(n) as we require extra space to store the generated reverse string.
3) Checking valid palindrome using regex method
This approach is the most pythonic way to solve valid palindrome pair problems. Regex abbreviated as the regular expression is the python in-built module consisting of various functions that can be used on the strings. To work with the regex model, you have to import it before starting the python program using the “import” keyword.
To check whether the string is a valid palindrome or not using a regular expression you have to make use of re.sub() on a set of alphanumeric characters which needs to be replaced with lowercase characters.
Python code using regular expression
The time complexity of the solution using this approach is O(n) where n is the total number of characters in the string. It is because you traverse each character of the string only once. The space complexity of this solution is O(1) as you don’t require any extra space to store the string.
Palindrome pairs are quite confusing to understand and hence are the best choice to test the programmer’s problem-solving ability. In this article, we understood three different approaches to solve the valid palindrome problem along with its python code and output.