This was kind of a weird problem, but the solution was kind of fun to write. Given a string, determine if it’s a palindrome and then write out all the possible permutations of palindromes that string potentially would have.
Here’s my solution:
import collections import itertools def palinpermute(s): s = s.replace(" ", "") c = collections.Counter(s) pivot = '' for k, v in c.iteritems(): if v % 2 != 0: if not pivot: pivot = k else: return (False, ) newStr = "" for k, v in c.iteritems(): if k != pivot: newStr += k*(v/2) palins = list() for c in itertools.permutations(newStr): palins.append("".join(c) + pivot + "".join(reversed(c))) return (True, palins)
Like a lot of the other solutions to string problems, we’re back to using the Counter again. In this case we use it to make certain that for each character, there has to be a matching one. If there isn’t a matching one, choose that character as a pivot point for our palindrome. Once we’ve selected a pivot point, there can’t be another one, so just return False and an empty list if we find one.
This next part is probably not obvious:
newStr = "" for k, v in c.iteritems(): if k != pivot: newStr += k*(v/2)
This generates a half of a palindrome which we’re going to use to find
all of the permutations. If we had the palindrome
tacocat, we would
end up with a string like
act here. When we call
that’s going to come up with a list which looks like
[('a', 'c', 't'),
('a', 'c', 't'), ('c', 'a', 't'), ('t', 'a', 'c'), ('c', 't', 'a'), ('t', 'c', 'a')].
Now it’s just a simple matter of joining each of these lists into new
strings around our pivot point (if we have one), and we’ve found each
of the potential palindromes.
The runtime complexity here comes down to how
works. The permutations come out in lexigraphical sort order, so
that’s at least n*log(n) average. Behind the scenes it’s doing something
more akin to
itertools.product() and filtering out repeated results,
which means this can get kind of ugly really quickly from a performance
I’m sure there are some interviewers out there who might think using
itertools.permutations() feels like cheating. My take on it when
I have interviewed candidates is that with very few exceptions it’s
fair game to use parts of any standard library for any given
programming language. Regardless, it’s not that hard to write
some kind of recursive function which generates the same list if
the interviewer is demanding it.