Ttdfjt

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"))

Nice implementation.

Here are a couple suggestions

collections.defaultdict

Intead of hashTable[i] = hashTable.get(i, 0) + 1, use collections.defaultdict

charcount = defaultdict(int)

for char in inputStr:
 charcount[char] += 1
actualCharactersInInput = len(inputStr) - charcount[' ']

collections.Counter

Or better yet, use a Counter:

charcount = collections.Counter(inputStr)
actualCharactersInInput = len(inputStr) - charcount[' ']

other

if actualCharactersInInput % 2:
 # odd number of chars
 return sum(count%2 for count in charcount.values()) == 1
else:
 # even number of chars
 return not any(count % 2 for count in charcount.values())

This looks correct! Here are my thoughts on the code:

• Per PEP-8, use snake_case for variable names and PascalCase for class names.


• Use Python builtins. Python makes frequency counting effortless using collections.Counter.


• Unused variable: lengthOfInputString. A static code analysis tool like a linter can spot this.


• Avoid variable names like hashMap. Something like freq_count, seen or char_count is clearer.


• Avoid using i as the loop block variable in for i in enumerable:. Reserve i for index variables and prefer something like c or elem that describes the variable more accurately.


• The function name, checkPalindromeAndPermutation, doesn't accurately describe what the function does, long as it is. I prefer is_palindrome_permutation or palindrome_permutation.


• Remove all print statements from your functions to avoid side effects.


• While I'm not a fan of inline comments, the comments in this program explain the logic nicely (typo and horizontal scrolling aside). Consider moving them to the function docstring, though, which summarizes the entire function neatly and gets out of the way of the code.


• 
  actualCharactersInInput can be replaced with len(s) assuming you don't mind stripping whitespace beforehand. Having a separate cached variable for holding len() is generally poor practice because the overhead of the function call is worth it to improve readability and reduce the risk of subtle bugs (len() and cached value going out of sync).


• Use foo += 1 instead of foo = foo + 1 to increment an integer.


• 
  

  Branching inside the for loop doesn't make much sense since the length of actualCharactersInInput is fixed. It makes more sense to pick a branch and stick to it as a human might do naturally if performing this task by hand.

  
  
  

  Instead of:

  
  
  

  for item in hashTable:
   if actualCharactersInInput % 2 == 0 and hashTable[item] % 2 != 0: 
   ...
   elif actualCharactersInInput % 2 == 1 and hashTable[item] % 2 == 1:
   #^^^ we can use elif since the conditional is disjoint
   ...
  

  
  
  

  try:

  
  
  

  if actualCharactersInInput % 2 == 0:
   for item in hashTable:
   if hashTable[item] % 2 != 0:
   ...
  else:
   for item in hashTable:
   if hashTable[item] % 2 == 1:
   ...
  

  
  
  

  Luckily, branch prediction will make the performance impact negligible even if we apply the conditional inside the loop, so this is mostly about reducing cognitive load on the programmer and isn't a hard-line rule.

  
  

Here's a possible re-write:

from collections import Counter

def permuted_palindrome(s):
 s = "".join(s.lower().split())
 odds = [x for x in Counter(s).values() if x % 2]

 if len(s) % 2 == 0:
 return len(odds) < 1

 return len(odds) < 2

This can cause a performance drop because of a lack of early return option. Benchmark the impact and make a call of performance vs brevity based on your use case.

I recommend validating correctness on any algorithm that's easily written using a clear-cut brute force method:

from collections import Counter
from itertools import permutations
from random import randint as rnd

def permuted_palindrome(s):
 ''' 
 Determines if a string is a permuted palindrome.
 A string is a permuted palindrome if:
 1. the string is of odd length and has 1 or fewer
 characters with an odd number of occurrences.
 - or - 
 2. the string is of even length and has no 
 characters with an odd number of occurrences.

 >>> permuted_palindrome("aaa")
 True
 >>> permuted_palindrome("aaab")
 False
 >>> permuted_palindrome("aaaab")
 True
 >>> permuted_palindrome("aaaabc")
 False
 >>> permuted_palindrome("aaaabcc")
 True
 '''
 s = "".join(s.lower().split())
 odds = [x for x in Counter(s).values() if x % 2]

 if len(s) % 2 == 0:
 return len(odds) < 1

 return len(odds) < 2

def brute_permuted_palindrome(s):
 return any(x == x[::-1] for x in permutations("".join(s.lower().split())))

if __name__ == "__main__":
 tests = 1000
 passes = 0

 for x in range(tests):
 s = "".join(chr(rnd(65, 70)) for x in range(rnd(1, 10)))

 if brute_permuted_palindrome(s) == permuted_palindrome(s):
 passes += 1

 print(f"passed passes/tests tests")

Randomization doesn't guarantee perfect coverage, but it's an easy way to be pretty certain your code works and can often catch edge cases that might be overlooked in enumeration (best to do both).

This snippet also shows how you might include a full docstring with doctests and uses the if __name__ == "__main__": guard which makes your module easily importable.

Revised from my C# version
Using a set instead of a dictionary or hashtable uses less space
We casefold to ignore case sensitivity and then by sorting this we can try to fail out early. If we have any more than 2 odd letters (which will happen any time we check a third unique char) then we fail out. But we don't want to fail when checking the second member, because it could possibly be removed.
If we didn't fail early we still want to make sure we have at most one odd letter. Therefore the final boolean comparison returns appropriately.

 def isPermutedPalindrome(input_string): 
 if (len(input_string) < 2):
 return True
 input_string = sorted(input_string.casefold())

 char_set = set()
 for letter in input_string:
 if letter == ' ':
 continue
 if letter in char_set:
 char_set.remove(letter)
 else:
 char_set.add(letter)
 if (len(char_set) > 2):
 return False
 return (len(char_set) < 2)