LeetCode 125: Valid Palindrome

code
two pointers
logging
easy
Author

spa-dev

Published

July 9, 2024

Problem Description

Difficulty: Easy

Given a string s, return True if it is a palindrome, otherwise return False.

A palindrome is a string that is identical when read from both directions, disregarding case differences and excluding all non-alphanumeric characters.

This problem is also known as “Is Palindrome” on NeetCode.

Examples:

Input: s = "Was it a car or a cat I saw?"
Output: true

Input: s = "tab a cat"
Output: false

Constraints:

1 <= s.length <= 1000
s consists of only printable ASCII characters.

Initial Solution

from typing import List
class InitialSolution:
    def isPalindrome(self, s: str) -> bool:
        # be sure not to use .isalpha :)
        clean_s = "".join(char.lower() for char in s if char.isalnum())

        for i, letter in enumerate(clean_s):
            if letter != clean_s[-1 - i]:
                return False
        else:
            return True
       
        #  In hindsight, the following would be cleaner,
        #  but not sure if it would allow us to return early?
        #  return clean_s == clean_s[::-1]
#  Test function is defined below
test_isPalindrome(InitialSolution)
Tests passed

Intial Results

My first attempt didn’t require too much effort to produce; however, I was disappointed to find it was rated in the bottom 40% for time and bottom 8% for memory. That initial string cleaning definitely cost me some time and memory. My poor attempt forced me to learn why these are called two-pointer algorithms! I basically have only one pointer (i), when we need two so they can act independently at each end of the string, cleaning (or ignoring) as we go.

  • Time complexity: \(O(n)\) for cleaning the string plus \(O(n)\) for the palindrome check, i.e., still \(O(n)\) overall.
  • Space complexity: \(O(n)\) due to the extra memory used by the clean string clean_s.

Let’s try again…

import logging

class Solution:
    def __init__(self):
        # Set up logging
        logging.basicConfig(level=logging.DEBUG, format="%(levelname)s: %(message)s")
        self.logger = logging.getLogger(__name__)

    def isPalindrome(self, s: str) -> bool:
        # Initialize pointers
        left = 0
        right = len(s) - 1

        self.logger.debug("Initial string: %s", s)
        self.logger.debug("Initial left pointer: %d, right pointer: %d", left, right)

        while left < right:
            while left < right and not s[left].isalnum():
                self.logger.debug(
                    "Skipping non-alphanumeric character at left %d: %s", left, s[left]
                )
                left += 1
            while right > left and not s[right].isalnum():
                self.logger.debug(
                    "Skipping non-alphanumeric character at right %d: %s",
                    right,
                    s[right],
                )
                right -= 1
            if s[left].lower() != s[right].lower():
                self.logger.debug(
                    "Characters do not match: %s != %s",
                    s[left].lower(),
                    s[right].lower(),
                )
                return False
            self.logger.debug(
                "Characters match: %s == %s", s[left].lower(), s[right].lower()
            )
            left += 1
            right -= 1
            self.logger.debug(
                "Updated left pointer: %d, right pointer: %d", left, right
            )
        else:
            self.logger.debug("String is a palindrome")
            return True
s = "No lemon, no melon"  # True
solution = Solution()
solution.isPalindrome(s)
DEBUG: Initial string: No lemon, no melon
DEBUG: Initial left pointer: 0, right pointer: 17
DEBUG: Characters match: n == n
DEBUG: Updated left pointer: 1, right pointer: 16
DEBUG: Characters match: o == o
DEBUG: Updated left pointer: 2, right pointer: 15
DEBUG: Skipping non-alphanumeric character at left 2:  
DEBUG: Characters match: l == l
DEBUG: Updated left pointer: 4, right pointer: 14
DEBUG: Characters match: e == e
DEBUG: Updated left pointer: 5, right pointer: 13
DEBUG: Characters match: m == m
DEBUG: Updated left pointer: 6, right pointer: 12
DEBUG: Skipping non-alphanumeric character at right 12:  
DEBUG: Characters match: o == o
DEBUG: Updated left pointer: 7, right pointer: 10
DEBUG: Characters match: n == n
DEBUG: Updated left pointer: 8, right pointer: 9
DEBUG: Skipping non-alphanumeric character at left 8: ,
DEBUG: Characters match:   ==  
DEBUG: Updated left pointer: 10, right pointer: 8
DEBUG: String is a palindrome
True

A note on logging

I used the built-in JupyterLab debugger to debug my initial attempt, but decided to add logging (above) to help visualize the code better after tripping up on various different edge cases. ChatGPT provided the logging statements, but I was curious why it used the old-style % formatting instead of f-strings…

Well, today I learned, be careful when using f-strings for logging, as the Python logging library was optimized to use %s formatting style. Although, you can add some extra code if you wish to use f-strings efficiently (see Stack Overflow discussion here and here as well as the Python documentation).

Clean version of code

The final clean version of my function is below. In LeetCode, this beat 68% of submissions on time and 77% on memory, so it’s much improved.

class CleanSolution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while right > left and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        else:
            return True
test_isPalindrome(CleanSolution)
Tests passed

Test function

def test_isPalindrome(solution_class):
    """Simple test function. Not extensive."""
    test_cases = [
        {"input": "A man, a plan, a canal: Panama", "expected": True},
        {"input": " ", "expected": True},
        {"input": ".,", "expected": True},
        {"input": "No lemon, no melon", "expected": True},
        {"input": "Was it a car or a cat I saw?", "expected": True},
        {"input": "tab a cat", "expected": False},
        {"input": "0P", "expected": False},
        {"input": "a", "expected": True},
        {"input": "a.", "expected": True},
    ]

    solution = solution_class()
    results = [solution.isPalindrome(test_case["input"]) for test_case in test_cases]
    expected = [test_case["expected"] for test_case in test_cases]

    if results == expected:
        print("Tests passed")
    else:
        print("Tests failed")
        print("Expected:", expected)
        print("Got:", results)

NeetCode Solution

NeetCode’s solution was essentially the same as above but used the following helper function instead of isalnum(). The complete solution is available via the NeetCode problem page.

# Helper function. Use within the Solution class
def alphaNum(self, c):
    return (
        ord("A") <= ord(c) <= ord("Z")
        or ord("a") <= ord(c) <= ord("z")
        or ord("0") <= ord(c) <= ord("9")
    )

Conclusion

The ‘clean’ solution discussed above has the following worst-case complexity:

  • Time complexity: \(O(n)\) as the checks ensure each character is processed only once by either pointer.
  • Space complexity: \(O(1)\) to store the pointers. No additional data structures are needed.