Valid palindrome solution

Question

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

Community · Accepted Answer · 2020-06-10 13:24:26Z

Some small nitpicks:

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
Here: ('a'<=source[i]<='z') you can remove the redundant parentheses and also write it like: source[i].isalnum()
It seems like you always forget to put a space between operators: i+=1 should be i += 1.
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

Graipher · Accepted Answer · 2016-12-14 08:26:31Z

4

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).

answered Dec 14, 2016 at 8:26

Graipher

41.7k7 gold badges70 silver badges134 bronze badges

Add a comment |

Stack Exchange Network

Valid palindrome solution

2 Answers 2

Some small nitpicks:

Reviewed code:

You must log in to answer this question.

Hot Network Questions

Valid palindrome solution

2 Answers 2

Some small nitpicks:

Reviewed code:

You must log in to answer this question.

Related

Hot Network Questions