CODEWITHSUNDEEP
python
garlfd
garlfd

Reputation: 149

Fast and pythonic way to find out if an anagram is a palindrome?

Given a string, how do we check if any anagram of it can be a palindrome?

For example let us consider the string "AAC". An anagram of it is "ACA" which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.

This is my current solution: 

from collections import defaultdict

def check(s):
    newdict = defaultdict(int)
    for e in s:
        newdict[e] += 1
    times = 0
    for e in newdict.values():
        if times == 2:
            return False
        if e == 1:
            times += 1
    return True

Any shorter solutions using the python library?

Upvotes: 1

Views: 2322

Answers (4)

Eric O. Lebigot
Eric O. Lebigot

Reputation: 94485

Here is shorter solution that uses the standard library, with a corrected algorithm (all the character counts must be even, except for at most one):

from collections import Counter
def check(s):
    return sum(1 for count in Counter(s).itervalues() if count % 2 == 1) <= 1

This is short but "slow", as the program goes through all the odd counts instead of stopping as soon as two are found. A faster solution that stops as soon as possible, is:

def check(s):
    odd_counts = (count for count in Counter(s).itervalues() if count % 2 == 1)
    try:
        next(odd_counts)  # Fails if there is no odd count
        next(odd_counts)  # Fails if there is one odd count
    except StopIteration:
        return True
    else:
        return False

Upvotes: 5

vermillon
vermillon

Reputation: 563

Even though it's not algorithmically the best, (if your strings are not extremely long it's not a problem), I'd like to provide a more readable solution.

from itertools import permutations

def has_palindrome(s):
    return any(c == c[::-1] for c in permutations(s,len(s)))

Upvotes: 0

James Sapam
James Sapam

Reputation: 16940

Without using Counter:

>>> def isit(s):
...     ls = [ x % 2 for x in [s.count(x) for x in set(s)]]
...     return [False, True][all(ls) or ls.count(1) == 1]
...
>>> isit('abc')
False
>>> isit('abb')
True
>>> isit('abbd')
False
>>> isit('abbdd')
True
>>> isit('abbdda')
True
>>>

Upvotes: 0

metatoaster
metatoaster

Reputation: 18908

This is probably better fit for code golfing, but eh it is quite trivial.

Observe that palindromes require a balanced set of sides, so you need generally even number of inputs per type. However a single odd item can be provided in the middle, so you can essentially raise that to a maximum of one set of characters that are odd. This can be done with a single list comprehension

>>> from collections import Counter
>>> def is_palindrome(letters):
...     return len([v for v in Counter(letters).values() if v % 2]) <= 1
... 
>>> is_palindrome('level')
True
>>> is_palindrome('levels')
False
>>> is_palindrome('levelss')
True

Oh wait, someone else beat with a solution, but that's what I got.

Upvotes: 2

Related Questions