June 30, 2018

Check if a string is a permutation of a palindrome in Python

By Mohammed Abualrob Algorithms and Data Structures, Code Snippets, Interview Questions 0 Comments

Problem

Implement an algorithm in Python to check if a given input string is a permutation of another palindrome string

Solution

If the number of occurrences of all characters in the string is even then the input string can be a permutation of a palindrome string. There is only once exception which is the character in the middle. This character can can either have odd or even count. For more details, take a look at the code snippet below…

Code

Here is the code in Python…

# Import python unit tests module
import unittest  

# This function returns true if the input 
# string is a permutation of another 
# palindrome string
def isPermPal(string):

	# We are going to use a dictionary to 
	# keep track of character frequency
	dic = {} 

	# Convert input string to lower case
	# and remove spaces
	string = string.lower()
	string = string.replace(" ", "")

	# Initialize character counts to 0
	for c in string:  
		dic[c] = 0  

	# Find character frequency
	for c in string:  
		dic[c]+= 1  

	# Find number of characters 
	# with even frequency
	num_even = 0
	for c, count in dic.items():  
		if count%2 == 0:
			num_even += 1

	# If input string is a permutation of a 
	# palindrome string then each character 
	# must have an even frequency except the 
	# one in the middle which can be either 
	# odd or even. In other words, the number
	# of characters with even frequency should
	# equal to the size of the dictionary or less
	# by 1. Recall the size of the dictionary
	# is the number of unique characters in the
	# input string because we used characters
	# as keys
	return num_even in (len(dic), len(dic)-1)

# This class uses python unit tests to test our code
class Tests(unittest.TestCase):    

	def test_case_01(self):
	 	self.assertFalse(isPermPal("cisco"))

	def test_case_02(self):                           
	    self.assertTrue(isPermPal("Rotator"))  

	def test_case_03(self):                           
	   self.assertTrue(isPermPal("Step on no pets"))

	def test_case_04(self):                           
	   self.assertTrue(isPermPal("No lemon no melon"))  

	def test_case_05(self):                           
	   self.assertTrue(isPermPal("Eva can I see bees in a cave"))  
 
# Run test suite
unittest.main()

# Import python unit tests module

import unittest

# This function returns true if the input

# string is a permutation of another

# palindrome string

def isPermPal(string):

# We are going to use a dictionary to

# keep track of character frequency

dic = {}

# Convert input string to lower case

# and remove spaces

string = string.lower()

string = string.replace(" ", "")

# Initialize character counts to 0

for c in string:

dic[c] = 0

# Find character frequency

for c in string:

dic[c]+= 1

# Find number of characters

# with even frequency

num_even = 0

for c, count in dic.items():

if count%2 == 0:

num_even += 1

# If input string is a permutation of a

# palindrome string then each character

# must have an even frequency except the

# one in the middle which can be either

# odd or even. In other words, the number

# of characters with even frequency should

# equal to the size of the dictionary or less

# by 1. Recall the size of the dictionary

# is the number of unique characters in the

# input string because we used characters

# as keys

return num_even in (len(dic), len(dic)-1)

# This class uses python unit tests to test our code

class Tests(unittest.TestCase):

def test_case_01(self):

self.assertFalse(isPermPal("cisco"))

def test_case_02(self):

self.assertTrue(isPermPal("Rotator"))

def test_case_03(self):

self.assertTrue(isPermPal("Step on no pets"))

def test_case_04(self):

self.assertTrue(isPermPal("No lemon no melon"))

def test_case_05(self):

self.assertTrue(isPermPal("Eva can I see bees in a cave"))

# Run test suite

unittest.main()

If you run the code above you should get something like:

# .....
# --------------------------------
# Ran 5 tests in 0.000s

# OK
# [Finished in 0.1s]

# .....

# --------------------------------

# Ran 5 tests in 0.000s

# OK

# [Finished in 0.1s]

Thanks for visiting. For feedback, please use the comments section below.

8 BIT AVENUE

Check if a string is a permutation of a palindrome in Python

More from my site

About Author

Mohammed Abualrob

Add a Comment