5
\$\begingroup\$

I'm working on this valid palindrome problem. Any advice on code bug, better idea for low algorithm execution time complexity, code style, etc. are highly appreciated.

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example

"A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note

Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

Source Code

def check_valid(source):
    i = 0
    j = len(source)-1
    source =source.lower()
    while i <= j:
        while i<=j and not ('a'<=source[i]<='z'):
            i+=1
        while i<=j and not ('a'<=source[j]<='z'):
            j-=1
        if i<=j:
            if source[i] != source[j]:
                return False
            else:
                i+=1
                j-=1
        if i > j:
            return True

if __name__ == "__main__":
    print check_valid('A man, a plan, a canal: Panama') # return True
    print check_valid('race a car') # return False
\$\endgroup\$
4
\$\begingroup\$

Some small nitpicks:

  1. Instead of i <= j you can stop before j by doing: i < j in the last two while loops. That way, you'll save one iteration per while. If you weren't constraint by: "For the purpose of this problem, we define empty string as valid palindrome" you might've remove that as well
  2. Here: ('a'<=source[i]<='z') you can remove the redundant parentheses and also write it like: source[i].isalnum()
  3. It seems like you always forget to put a space between operators: i+=1 should be i += 1.
  4. Add docstrings to your function

Reviewed code:

def check_valid(source):
    """ Return True/False if a string is a palindrome """

    i, j, source = 0, len(source) - 1, source.lower()
    while i <= j:
        while i < j and not source[i].isalnum():
            i += 1
        while i < j and not source[j].isalnum():
            j -= 1
        if i <= j:
            if source[i] != source[j]:
                return False
            else:
                i += 1
                j -= 1
        if i > j:
            return True


if __name__ == "__main__":
    print check_valid('A man, a plan, a canal: Panama')  # return True
    print check_valid('race a car')  # return False
\$\endgroup\$
4
\$\begingroup\$

The pythonic way to check for a palindrome is using s[::-1] == s, i.e. a negative step for the slice operator.

With your additional constraints your code could be:

def check_valid(source):
    l = [c.lower() for c in source if c.isalnum()]
    return l[::-1] == l

Note that this uses an additional O(2m) memory, because it copies the string effectively twice (once to form the list with m alphanumeric characters out of the n characters in the input string and another when reversing it).

\$\endgroup\$

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.