Data Structures

What will we cover in this tutorial?

How can you check if a string is a palindrome. Obviously this can be done in various creative ways. In this tutorial we will use a Queue and a Stack to solve it.

Step 1: What is a palindrome?

A palindrome is a sequence of characters which reads the same backward as forward.

Common examples are:

• racecar

Where you notice that RACECAR has the same sequence of characters, whether you read it from left-to-right, or from right-to-left.

Also, palindromes are also considered with dates. Examples could be:

• 11/11/11 11:11
• 02/02/2020

If sentences are considered as palindrome, often the spaces, punctuation, and upper/lowercase variations are ignored. Examples could be:

• “Sit on a potato pan, Otis”
• “Able was I, ere I saw Elba.”

Step 2: A simple implementation to test palindrome

Let’s start with understanding how we can check if sequence of characters is a palindrome by using a Stack and a Queue.

If you are new to a Stack, then we can propose you read this tutorial or this.

Also, if you are not familiar with a Queue, then we propose you read this tutorial or this.

When we insert into a Stack and Queue, they will be removed in opposite orders.

Wow. That is a great idea. Why not add (push and enqueue) all characters on a Stack and Queue. Say, we do that for madam.

Then they the order of removal (pop and dequeue) will give the same elements, as it is a palindrome. If it was not a palindrome, say “12345“, then the elements removed from simultaneously from the Stack and Queue would not be identical.

This leads to the following piece of code, where we have included implementations of a Queue and Stack. See this tutorial for Stack and this tutorial for a Queue, if you need explanation of the code.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node

class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element

def is_empty(self):
return self.stack == None

def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
if self.tail == self.head:
self.tail = self.head = None
else:
return element

def is_empty(self):
return self.head is None

def __str__(self):
if self.head is None:
return None
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

def is_palindrome(s):
stack = Stack()
queue = Queue()
for c in s:
stack.push(c)
queue.enqueue(c)

print(stack)
print(queue)

while not stack.is_empty():
if stack.pop() != queue.dequeue():
return False

return True

print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))
```

This would result in the following output.

```[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False
```

Step 3: Make it work on for general strings

The above code does not work if we encounter a string like, “Sit on a potato pan, Otis.

One way to deal with this is to have a function in front of the is_palindrome from previous step.

This function can convert the format of a sequence of characters to the format that is_palindrome will require. This is a nice way to break down functionality in your code and not overcomplicate functions.

Let’s try that. We will rename is_palindrome to _is_palindrome, to indicate that it is not to be used.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node

class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element

def is_empty(self):
return self.stack == None

def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
if self.tail == self.head:
self.tail = self.head = None
else:
return element

def is_empty(self):
return self.head is None

def __str__(self):
if self.head is None:
return None
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

def _is_palindrome(s):
stack = Stack()
queue = Queue()
for c in s:
stack.push(c)
queue.enqueue(c)

print(stack)
print(queue)

while not stack.is_empty():
if stack.pop() != queue.dequeue():
return False
return True

def is_palindrome(s):
s = s.lower()
r = ""
for c in s:
if c in "abcdefghijklmnopqrstuvwxzy1234567890":
r += c
return _is_palindrome(r)

print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))
print(is_palindrome("Sit on a potato pan, Otis"))
print(is_palindrome("Able was I, ere I saw Elba."))
print(is_palindrome("Able was I, where I saw Elba."))
```

Which will result in the following output.

```[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False
[m a d a m i m a d a m]
[m a d a m i m a d a m]
True
[s i t o n a p o t a t o p a n o t i s]
[s i t o n a p o t a t o p a n o t i s]
True
[a b l e w a s i e r e i s a w e l b a]
[a b l e w a s i e r e i s a w e l b a]
True
[a b l e w a s i e r e h w i s a w e l b a]
[a b l e w a s i w h e r e i s a w e l b a]
False
```

Rune

Share
Rune

The Best Free Data Science Course Online

Data Science for beginners in this free online course Data Science is over complicated by…

2 months ago

The Ultimate 15 Machine Learning Projects With Source Code

15 Machine Learning Projects That Will Teach You All You Need as Machine Learning Authority…

2 months ago

Learn Python FREE Online

Why learn Python? There are many reasons to learn Python, and that is the power…

2 months ago

How to Check if a Number is Even or Odd with Python

What will you learn? How to use the modulo operator to check if a number…

2 months ago

The Truth About Being a Python Software Contractor

There are a lot of Myths out there There are lot of Myths about being…

4 months ago

Do This and 10X Your Salary as a Software Engineer

To be honest, I am not really a great programmer - that is not what…

4 months ago