Valid Palindrome

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def isPalindrome(self, s: str) -> bool:

        i, j = 0, len(s) - 1

        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1

            if s[i].lower() != s[j].lower():
                return False

            i += 1
            j -= 1

        return True

Identifying Problem Isomorphism

“Valid Palindrome” can be mapped to the following problems:

  1. “Palindrome Number” (#9) on LeetCode
  2. “Valid Palindrome II” (#680) on LeetCode

Reasoning:

These problems involve checking if a sequence, string or number, is a palindrome.

  1. “Palindrome Number” is the simplest problem, where you are asked to determine if an integer is a palindrome. It’s simpler because you don’t have to handle the additional complexity of non-alphanumeric characters or case sensitivity.

  2. “Valid Palindrome II” is a more complex problem, as it allows for the removal of one character in the string to see if a valid palindrome can be created. It builds on the concept of checking for a palindrome and adds an additional layer of complexity in that you may modify the sequence slightly to form a valid palindrome.

While these problems are not exact isomorphs of “Valid Palindrome,” they all revolve around the same core concept of checking if a sequence is a palindrome.

10 Prerequisite LeetCode Problems

“Valid Palindrome” (LeetCode 125) is a straightforward problem and is a good starting point for learning about string manipulation and the two-pointer technique. It requires very little in terms of prerequisite knowledge or skills.

Here are a few simpler problems, focusing on string manipulation:

  1. “344. Reverse String”: This problem is even simpler than “Valid Palindrome”, asking you to reverse a string, which can be done with a straightforward loop.
  2. “709. To Lower Case”: This problem requires you to change all characters in a string to lowercase.
  3. “771. Jewels and Stones”: This problem requires counting the occurrences of characters from one string in another string.
  4. “804. Unique Morse Code Words”: This problem involves converting strings to Morse code and counting unique results.
  5. “806. Number of Lines To Write String”: This problem involves calculating the number of lines needed to write a string given constraints on line length.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	i, j = 0, len(s) - 1
    	while i < j:
    		a, b = s[i].lower(), s[j].lower()
    		if a.isalnum() and b.isalnum():
    			if a != b: return False
    			else:
    				i, j = i + 1, j - 1
    				continue
    		i, j = i + (not a.isalnum()), j - (not b.isalnum())
    	return True

Problem Classification

  1. String Manipulation: The task involves working with a string input, s, and traversing it to validate a condition, which is a fundamental operation of string manipulation.

  2. Two Pointers Technique: The algorithm uses two pointers, i and j, which traverse the string from both ends towards the center. The two-pointer technique is a common strategy for solving array and string-related problems, particularly when the order or sequence of the elements plays a crucial role in the problem.

  3. Palindrome Check: The main goal of this problem is to determine whether a given string is a palindrome or not, ignoring spaces, punctuation and case sensitivity. Palindromes are a common theme in problems involving strings.

  4. Character Properties: The problem involves checking whether each character is alphanumeric. This falls under understanding and manipulating the properties of characters in a string.

These categories can help to find similar problems for practice or to identify appropriate problem-solving techniques and algorithms.

Language Agnostic Coding Drills

  1. Variable Assignments:

    • Declare variables of various types (integers, floats, strings, boolean etc.)
    • Perform various operations on variables (addition, multiplication, division, subtraction)
    • Swap the values of two variables without using a third variable

  2. Control Structures:

    • Write a code snippet to check if a number is even or odd (if-else statement)
    • Write a code snippet to find the maximum of three numbers (nested if-else)

  3. Loops:

    • Print numbers from 1 to 10 using a loop
    • Write a loop to calculate the factorial of a number
    • Write a loop to print a Fibonacci series up to a certain number

  4. Functions:

    • Write a function that takes two numbers as parameters and returns their sum
    • Write a recursive function to calculate the factorial of a number
    • Write a function to check if a string is palindrome

  5. Data Structures:

    • Create a list/array and perform basic operations (insert, delete, access)
    • Create a dictionary/hashmap and perform basic operations (insert, delete, access)
    • Implement a stack or a queue and demonstrate the push/pop or enqueue/dequeue operations

  6. Sorting and Searching Algorithms:

    • Implement a linear search algorithm
    • Implement a binary search algorithm
    • Implement basic sorting algorithms like bubble sort, selection sort, or insertion sort

  7. Classes and Objects (for OOP languages):

    • Create a basic class with a constructor, some fields, and methods
    • Instantiate objects of the class and manipulate fields and methods
    • Write a class that inherits from another class and demonstrate method overriding

Targeted Drills in Python

  1. Working with Strings: Understand the basics of how strings work in Python, how to access characters in a string through indexing, and how to determine the length of a string. Implement simple operations like lower-casing all characters in a string.
1
2
3
4

s = "Hello World"
print(len(s))  # Print length of string
print(s[0])  # Print first character
print(s.lower())  # Convert string to lowercase
  1. String Traversal: Understand how to traverse a string using loops, especially focusing on traversing from both ends towards the middle.
1
2
3
4
5
6

s = "Hello World"
i, j = 0, len(s) - 1
while i < j:
    print(s[i], s[j])  # Print characters from both ends
    i += 1
    j -= 1
  1. Character Classification: Understand how to classify characters in Python, especially distinguishing alphanumeric characters (letters and digits) from other characters.
1
2
3
4
5
6
7
8

c = 'a'
print(c.isalnum())  # Check if character is alphanumeric

c = '1'
print(c.isalnum())  # Check if character is alphanumeric

c = '!'
print(c.isalnum())  # Check if character is alphanumeric
  1. Comparing Characters: Understand how to compare characters in Python, and how to handle comparison of characters with different cases.
1
2
3
4
5
6
7

a = 'a'
b = 'a'
print(a == b)  # Compare same case characters

a = 'a'
b = 'A'
print(a.lower() == b.lower())  # Compare different case characters
  1. Boolean Operations: Understanding boolean operations is crucial for the conditional statements in this problem. Practice using boolean logic in Python and applying it in conditional statements.
1
2
3

print(True and False)  # And operation
print(True or False)  # Or operation
print(not True)  # Not operation

Once comfortable with these smaller coding exercises, one can start to combine these concepts and work towards the final solution, where you traverse the string from both ends, ignoring non-alphanumeric characters and comparing the alphanumeric ones. If at any point the characters do not match, you return False, and if you manage to traverse the whole string this way, you return True.

My Notes

title: Valid Palindrome excerpt: This covers the basic building blocks Alphanumeric Check and Two Pointers Moving Towards Each Other. tags: palindrome alphanumeric-check two-pointers-moving-towards-each-other

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

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def alphanumeric?(c)
  if c == ',' || c == ' ' || c == ':' || c == '.'
    return false
  end
  
  if c.downcase =~ /^[A-Z0-9]+$/i
    return true
  else
    return false
  end  
end

def is_palindrome(s)
  i = 0
  j = s.size - 1
  
  while i < j
    while i < j && !alphanumeric?(s[i])
      i += 1
    end

    while i < j && !alphanumeric?(s[j])
      j -= 1
    end

    if s[i].downcase != s[j].downcase
      return false
    end

    i += 1
    j -= 1
  end
  
  return true
end

s = ".,"
p is_palindrome(s)

Building Blocks

  • Alphanumeric Check
  • Two Pointers Moving Towards Each Other