I’ve Got It Backwards — Leetcode — Palindrome

Photo by dylan nolte on Unsplash

https://bit.ly/lc-valid-palindrome-20200803

Valid Palindrome

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

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false

Palindrome: noun

a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.

I solved this two different ways. The first way was faster than about 52% of other submissions. The second way was faster than 97.14% of other submissions, although when I ran my timing tests locally, which one was faster varied.

1. Case isn’t important, so lower or upper everything. Doesn’t matter.

s.lower()
or 
s.upper()

2. The characters to be compared have to be alpha OR numeric, so the rest have to be filtered. Use isalnum, rather than both isalpha and isdigit to filter out everything else, including spaces.

s.isalnum() returns True or False

3. The resulting string from the first two needs to be the same forward or backwards. There are a variety of ways to reverse a string. For example, convert it to a list sList,and then reverse it list this:

revList = list(reversed(strList))
or
revList = strList[::-1]

Solution One (Faster than 52ish% of other submissions)

sList = [i.lower() for i in s if i.isalnum()]
sRevList = list(reversed(sList))
return all(map(lambda x, y: x == y, sList, sRevList))

Line 1

The first line is a list comprehension. It lowers each letter if it’s alpha or numeric, and returns the result as a list to sList

sList = [i.lower() for i in s if i.isalnum()]

Line 2

The second line uses reversed, which returns an iterable object for whatever’s inside the reversed call. Then, I wrapped it in a list() call, to store the results from reversed in a new list called sRevList.

Line 3 — Broken Down

First: The inner most part of this line uses a lambda function to compare the elements in the original and reversed lists, to see if they’re the same.

(lambda x, y: x == y, sList, sRevList) 

I think of lambda as a quick, concise function definition. It’s often only used once where it’s defined. But it can be reused if it’s assigned to a variable name.

Second: The map()wrapper around the lambda function returns a sequence of the results from the lambda function, ie, a sequence of True / False results for the character by character comparisons.

map(LAMBDA FUNCTION)

Third: The all() wrapper around the map function returns a single result for the sequence of results produced by map(). If any of the map results are False, all() returns False. Otherwise, it returns True, which means the string is a palindrome.

all(map(LAMBDA FUNCTION))

Solution 2: (Faster than 97.14% of submissions)

This solution was really just a combining the elements of Solution 1, so they used less storage space, and cut out some of the functions that organized and compared those intermediate results. The following two lines were the full code for Solution 2:

xList = [x for x in s.lower() if x.isalnum()]
return (lambda x: x == x[::-1])(xList)

Line 1

The first line uses a list comprehension again, to convert each letter to lowercase, and it filters out anything that isn’t alphanumeric.

Line 2 — Broken Down

The second line is a lambda function definition again. The lambda function is applied to the list from the first line xList.

Break Down of Line 2

First: x[::-1] is another way of reversing a list. The lambda function is comparing each character in the list to the same slot at the other end of the list. ie, index 0 gets compared to the last item index, which is -1 in python. Then index 1 gets compared to -2, etc.

Second: The lambda function definition at the beginning of this line gets applies to the xList created in the previous line.

Line 2 could also have been split into two lines. Then Solution 2 would have looked like this:

xList = [x for x in s.lower() if x.isalnum()]
compareChars = (lambda x: x == x[::-1])
return compareChars(xList)

If this helps you, let me know! If there’s something you know of that could have been done better, faster, cheaper, I hope you’ll share that, too! I’m always here to learn.