I am indeed fascinated by data structures and algorithms. Besides the fact that they form part of the foundations of programming, landing your first job as a data scientist or a developer might depend on your ability to write a code to implement an algorithm. This could be searching, sorting, tree-traversal and a host of other algorithms. It sure takes constant practice to get a hang of the basic types. Checking if a string is a palindrome is a popular interview problem. In this article I will give you two methods to solve this problem using python built-in modules.
The queue is data structure akin to a queue of customers in an ice cream shop. In this scenario, customers join the queue at the rear and exit at the front of the line after been served.
The ordering of the queue is First In First Out (FIFO) as opposed to the Last In First Out (LIFO) ordering in a stack. A double ended queue is a unique implementation of a queue in which there is the possibility to remove items from the front and the rear.
Implementing a double ended queue class.
The three methods of the queue are
- enqueue: used to insert items onto a queue (same as the push method of a stack).
- dequeue: used to delete items from the queue (same as the pop method of a stack).
- isempty: used to check if the queue still contains items (same as the size attribute of a stack) To understand how the double ended queue works, let us implement a double eneded queue class.
class DeQueue:
def __init__(self, queue):
self._queue = list(queue)
def getqueue(self):
return self._queue
def enqueue(self, item):
return self._queue.append(item)
def dequeue_left(self):
return self._queue.pop(0)
def dequeue_right(self):
return self._queue.pop(-1)
def isEmpty(self): #method to tell if the queue is empty
return(len(self._queue) == 0)
Now we instantiate our class to create a DeQueue object and run an example to see if it works.
dq = DeQueue(range(10))
for i in range(10, 15):
dq.enqueue(i)
v = dq.dequeue_left()
print(dq.getqueue())
# results
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
The built-in collections module provides a beautiful deque class.
from collections import deque
dq = deque(range(10))
dq
# results
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
We repeat the above example to see if we get the same results.
for i in range(10, 15):
dq.append(i)
v = dq.popleft()
print(dq)
# and for sure we get the same output as our class
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
deque([3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
deque([4, 5, 6, 7, 8, 9, 10, 11, 12, 13])
deque([5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Having describe in brief how the double ended queue works, lets try to implement our palindrome checker using the deque class from collections module. We also import the ascii_lowercase to filter out just letters or the alphabet and ignore punctuations - this makes our palindrome checker very robust.
The implementation is as follows:
- First, we load our string, or numbers, and we check the type since numbers can also be palindromic for example 1221, 1234321.
- If the character is a letter of the alphabet, we convert to a lower case character
- Then we loop through using a while loop to check the length of the letters. While the loop runs, we pop from both sides and compare the resulting characters.
- Finally we return false if the characters do not match and True otherwise
- The magic function %%file enables us to write the code to a .py file.
%%file palindrome.py
from collections import deque
from string import ascii_lowercase
def palindrome(sentence):
letters = deque() # we start with an empty
for char in sentence:
if isinstance(char, int):
letters.append(char)
else:
char = char.lower()
if char in ascii_lowercase:
letters.append(char)
while len(letters) > 1:
if letters.popleft() != letters.pop():
return False
return True
To test our palindrome checker, I have gathered a list of palindromes in a text file named 'palindrome.txt'
with open('palindrome_template.txt') as fh:
print("we have {} palindromes".format(sum(1 for line in fh)))
for lnum, line in enumerate(fh):
if lnum > 10:
break
print(line[:-1])
# result
we have 19 palindromes
with open('palindrome_template.txt') as fh:
for lnum, line in enumerate(fh):
if lnum > 10:
break
print(line[:-1])
# results
Are we not pure? 'No, sir!' Panama's moody Noriega brags. 'It is garbage!' Irony dooms a man-a prisoner up to new era.
Are we not drawn onward, we few, drawn onward to new era?
Never odd or even.
Stressed desserts
racecar
kayak
Writing a unit test for our functions
Our unit test will be carried out using pytest. The following code illustrates the unit test implementation. The setup_class method is performed once for the whole class while the teardown method cleans up the state after our test.
%%file test_palindrome.py
import pytest, os, shutil
import palindrome
class TestPalindrome(object):
pal_file_template = 'palindrome_template.txt'
pal_file_testor = 'pal_test.txt'
def setup_class(self):
shutil.copy(TestPalindrome.pal_file_template, TestPalindrome.pal_file_testor)
def teardown_class(self):
os.remove(TestPalindrome.pal_file_testor)
def test_words(self):
new_dromes = [str(line) for line in open(TestPalindrome.pal_file_testor)]
for new_drome in new_dromes:
assert palindrome.palindrome(new_drome) == True
Bonus implementation - Using the SequenceMatcher from the difflib module.
In this bonus example, I use the Sequencematcher from the difflib module to execute the same palindrome checker. However I will not go into details of how this works. Basically, we strip punctuations using the maketrans(). Then we compare a string and its reversed form and return True if both strings have a match of 1 or return False if the match is less than 1.
import difflib, string
def my_palindrome(str):
trans = str.maketrans('', '', string.punctuation)
str = str.lower().translate(trans)
s1 = str.replace(' ', '')
s2 = s1[::-1]
match = difflib.SequenceMatcher(None, s2, s1, False).ratio()
if match != 1:
return False
return True
Let's test our second function:
long_str = "Are we not pure? 'No, sir!' Panama's moody Noriega brags. 'It is garbage!' Irony dooms a man-a prisoner up to new era."
my_palindrome(long_str)
# result
True
I hope you learnt something and I hope this post was not too long. I look forward to receiving your feedback so I could improve future posts.
#Staysafe.
Top comments (1)
This is an awesome post. I found it really helpful.
Thanks richinex.