Skip to main content
Tweeted twitter.com/StackCodeReview/status/1160793087788105728
Became Hot Network Question
edited tags
Link
200_success
  • 145.7k
  • 22
  • 191
  • 481
Source Link

CTCI Chapter 1 : Palindrome Permutation

Below is my code for the problem 1.4 in CTCI. I would like a review of my code and if my approach to the problem is correct.

Problem Statement: Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE

Input: Tact Coa

Output: True (permutations:"taco cat'; "atco cta'; etc.)

My Solution (Python):

def checkPalindromeAndPermutation(inputstr):
    lengthOfInputString = len(inputstr)
    counterforodd = 0
    actualCharactersInInput = 0
    inputstr = inputstr.lower()
    hashTable = dict()
    
    for i in inputstr:
        if i != " ":
            hashTable[i] = hashTable.get(i, 0) + 1
            actualCharactersInInput = actualCharactersInInput + 1
    print(hashTable)

    for item in hashTable:
        # if input has even length, but each character's frequency is not even, then it's not a plaindrome
        if actualCharactersInInput % 2 == 0 and hashTable[item] % 2 != 0: 
            return False
        # if input has odd length, but more than one character's frequency is greater than 1 , then it's not a plaindrome
        if actualCharactersInInput % 2 == 1 and hashTable[item] % 2 == 1:
            counterforodd = counterforodd + 1
            if counterforodd > 1:
                return False
    return True
    

print("Answer : " , checkPalindromeAndPermutation("abc bac"))