4
\$\begingroup\$

This is a solution to exercise 1.4 from Cracking the Coding Interview written using Python 3.

Given a string, write a function to check if it is a permutation of a palindrome.

Example: 'Tact Coa'

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

I wanted to get feedback on making my code clearer and more pythonic. I believe my code has time complexity \$O(n)\$ and space complexity \$ O(n)\$ is that correct? If so, is there any way to improve on either the space or time complexity?

from collections import Counter


def is_palindrome_permutation(data: str) -> bool:
    """Given a string, check if it is a permutation of a palindrome."""
    data = data.lower().replace(' ', '')
    num_odd = sum(1 for char, freq in Counter(data).items() if char != ' ' and freq % 2 == 1)
# Check for two types of palindromes , 1) Odd Length (e.g. abc cba) 2) Even Length (e.g. abc d cba)
    if num_odd == 1 and len(data) % 2 == 1 or num_odd == 0 and len(data) % 2 == 0:
        return True
    else:
        return False

Test

datum = 'Tac4t co@A @4'

print(is_palindrome_permutation(datum))

Result

True

Test

datum = 'Tac4t co@A @4s'

print(is_palindrome_permutation(datum))

Result

False

\$\endgroup\$
5
\$\begingroup\$

Some suggestions:

  1. You strip out spaces, then on the next line check if each character is a space. The second part is redundant.
  2. The only possible values for freq % 2 are 0 and 1, so num_odd = sum(1 for char, freq in Counter(data).items() if char != ' ' and freq % 2 == 1) can be simplified as num_odd = sum(freq % 2 for Counter(data).values())
  3. If num_odd is 0, then there must be an even number of elements. If num_odd is 1, then there must be an odd number of elements. So really all you care about is if there is more than 1 odd count.
  4. You can return the results of expressions directly. So something like return x < y is simpler than using an if test and manually returning True or False depending on the outcome.
  5. I would put the replace first since that reduces the number of characters that lower has to operate over (although this is probably a silly negligible micro optimization).

So the code can be simplified to:

from collections import Counter


def is_palindrome_permutation(data: str) -> bool:
    """Given a string, check if it is a permutation of a palindrome."""
    data = data.replace(' ', '').lower()
    return sum(freq%2 for freq in Counter(data).values()) < 2

One more thing you could do is put the Counter on the first line. I think this hurts readability a bit, but does mean that your modified data can be garbage collected right away. There is no point doing this with .values(), though, since this is just a view into the Counter object, so the Counter object has to be kept in memory.

from collections import Counter


def is_palindrome_permutation(data: str) -> bool:
    """Given a string, check if it is a permutation of a palindrome."""
    data = Counter(data.replace(' ', '').lower())
    return sum(freq%2 for freq in data.values()) < 2
\$\endgroup\$
3
\$\begingroup\$
if num_odd == 1 and len(data) % 2 == 1 or num_odd == 0 and len(data) % 2 == 0:

is a long way to say

if num_odd == len(data) % 2:

if condition:
    return True
else:
    return False

is a long way to say

return condition

You don't need to check that char != ' ': you already filtered them out one line above. In any case, stick to a Single Responsibility Principle. If you count odd occurrences, just count them.

\$\endgroup\$
  • \$\begingroup\$ do you recommend changing num_odd to odd_occurences? \$\endgroup\$ – newToProgramming Sep 16 '16 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.