6
\$\begingroup\$

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"))
\$\endgroup\$
  • 1
    \$\begingroup\$ The logic can be simplified. You only need to verify that at most 1 character has an odd count. \$\endgroup\$ – Florian F Aug 12 at 11:28
7
\$\begingroup\$

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())
\$\endgroup\$
  • \$\begingroup\$ Thank you so much, I learned something new today :) \$\endgroup\$ – Manas Tripathi Aug 12 at 2:21
  • \$\begingroup\$ You can "smarten" the final check. If the length is odd there must be 1 character with an odd frequency. If the length is even there must be 0 characters with an odd frequency. Change not any(count % 2 for count in charcount.values()) to sum(count%2 for count in charcount.values()) == 0. Then the check is one line return sum(count%2 for count in charcount.values()) == actualCharactersInInput % 2 \$\endgroup\$ – spyr03 Aug 12 at 14:19
  • \$\begingroup\$ @spyr03, I thought of that too, but opted to use not any(...) because it would stop when it found the first odd count rather than sum the entire list. Probably a case of premature optimization. \$\endgroup\$ – RootTwo Aug 12 at 18:38
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Waow, Thank you for a detailed explanation. This is very helpful. \$\endgroup\$ – Manas Tripathi Aug 12 at 2:21
  • \$\begingroup\$ Why ` s = "".join(s.lower().split())` instead of s.lower() or s.casefold(). And if you do odds = sum(x % 2 for x in Counter(s).values()),you don't need the len, and can do return odds < 1 + (len(s) % 2) \$\endgroup\$ – Maarten Fabré Aug 12 at 8:48
  • \$\begingroup\$ You can reduce the return logic to return len(odds) == len(s) % 2. Even length strings can have no odds, while odd length strings can have one. \$\endgroup\$ – spyr03 Aug 12 at 14:22
  • \$\begingroup\$ Thanks for the feedback. s = "".join(s.lower().split()) removes whitespace and lowers the string. After removing whitespace, the rest of the logic is much cleaner, and this handles more than just spaces. I kept len over sum because sum seemed to obfuscate the logic a bit. return len(odds) == len(s) % 2 seems reasonable but I think going terser at this point has diminishing returns. \$\endgroup\$ – ggorlen Aug 12 at 14:51
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ When answering a question, you should at least try to review the original code in some way or another. Answering in a different language is also confusing and should be avoided. \$\endgroup\$ – dfhwze Aug 15 at 19:54
  • 1
    \$\begingroup\$ Ok, I wasn't sure how to do it in Python right away, so here's the converted snippet. \$\endgroup\$ – Drubuntu Aug 15 at 22:57
  • 1
    \$\begingroup\$ Thank's for taking the time to convert the snippet. Could you also explain the differences between your snippet and OP code to make us understand why your solution could be better? \$\endgroup\$ – dfhwze Aug 16 at 7:12
  • \$\begingroup\$ In python, a set would be a more natural datastructure for this char_list than a list. And the letter is ' ' only works because CPython interns a number of strings that occur a lot. letter == ' ' is more universally correct \$\endgroup\$ – Maarten Fabré Aug 16 at 7:17
  • \$\begingroup\$ Thanks for the feedback everyone! \$\endgroup\$ – Drubuntu Aug 16 at 18:27

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.