Another LeetCode Blog Post

October 6, 2024

We're solving another LeetCode problem today. Tomorrow I will add my new project. Let's dive in.

The Problem

Today's problem is 9. Palindrome Number. The problem is as follows: Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1: Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left. Example 2:

Example 2: Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

The Solution

Let's answer using the UMPIRE method:

• Understand
  • We are given an integer, and we are to determine if it is a palindrome.
  • In an interview. I would ask if we can solve this using strings or if I should solve it mathematically.
• Match
  • We can match this problem to a math problem or string problem.
• Plan
  • We can write a function which casts the number a string, and it will check if the first and last digits are the same until there is 1 or less digits.
• Implement

Copy
1class Solution:
2    def isPalindrome(self, x: int) -> bool:
3        def recursivePalindrome(s: str) -> bool:
4            if len(s) <= 1:
5                return True
6            elif s[0] != s[-1]:
7                return False
8            return recursivePalindrome(s[1:-1])
9        
10        return recursivePalindrome(str(x))

• Review
  • We implemented this using a locally defined recursive function.
  • We can test our code using the examples provided.
  • x = 121
    • return True

Copy
1def test_isPalindrome(self):
2        assert self.test_isPalindrome(1221)
3        assert not self.test_isPalindrome(31)

• Evaluate
  • Our code runs in O(n) time complexity due the call being done n/2 times.
  • Our space complexity is O(n) as we are storing the string in memory each time we recursively call.
    • We can reduce the complexity to constant space by using pointers.

Copy
1def isPalindrome(x: int) -> bool:
2        s = str(x)
3        left = 0
4        right = len(s) - 1
5        while left < right:
6            if s[left] != s[right]:
7                return False
8            left += 1
9            right -= 1
10        return True

LeetCode as Procrastination

Intro to Cursor