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.