Valid Palindrome Problem with Python Solution

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

class Solution:
   def isPalindrome(self, string: str):
       '''
       A function to check if a sequence is Palindrome or not!
       :param string: Sequence to be checked
       :return: True if it is palindrome else False
       '''
       sequence=""
       for i in string:
           if i.isalpha():
               sequence+=i
           elif i.isdigit():
               sequence+=i
       sequence=sequence.lower()
       for i in range(len(sequence)//2):
           if sequence[i] != sequence[len(sequence)-1-i]:
               return False
       return True
  
if __name__ == '__main__':
   string = 'Was it a car or a cat I saw!!'
   print(f'Is "{string}" a palindrome? : {Solution().isPalindrome(string)}')
   string2 = 'A man, a plan,'
   print(f'Is "{string2}" a palindrome? : {Solution().isPalindrome(string2)}')

Output

Is "Was it a car or a cat I saw!!" a palindrome? : True
Is "A man, a plan," a palindrome? : False

Time complexity

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

class Solution :
   def isPalindrome(self, string: str ) :
       '''
       A function to check if a string is Palindrome or not!
       :param string: string to be checked
       :return: True if it is palindrome else False
       '''
       string = string.lower()
       s_stripped = ''.join(list( filter ( lambda x : x.isalnum () == True , string)))
       return s_stripped == s_stripped[::-1]


if __name__ == '__main__' :
   string = 'Was it a car or a cat I saw!!'
   print (f'Is "{string}" a palindrome? : {Solution ().isPalindrome (string)}')
   string2 = 'A man, a plan,'
   print (f'Is "{string2}" a palindrome? : {Solution ().isPalindrome (string2)}')

Output

Is "Was it a car or a cat I saw!!" a palindrome? : True
Is "A man, a plan," a palindrome? : False

Time complexity

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

import re
class Solution :
   def isPalindrome(self, string: str ) :
       '''
       A function to check if a string is Palindrome or not!
       :param string: string to be checked
       :return: True if it is palindrome else False
       '''
       # Remove all the white spaces and special charcters
       string = ''.join(re.findall(r'[a-zA-Z0-9]', string))
       return string.lower() == string[::-1].lower()

if __name__ == '__main__' :
   string = 'Was it a car or a cat I saw!!'
   print (f'Is "{string}" a palindrome? : {Solution ().isPalindrome (string)}')
   string2 = 'A man, a plan,'
   print (f'Is "{string2}" a palindrome? : {Solution ().isPalindrome (string2)}')

Output

Is "Was it a car or a cat I saw!!" a palindrome? : True
Is "A man, a plan," a palindrome? : False

Time complexity

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.

Conclusion

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.