NUHMAN.com

Introduction

LeetCode 125: Valid Palindrome is a string manipulation problem that requires checking whether a given string is a valid palindrome, considering only alphanumeric characters and ignoring spaces, punctuation, and case sensitivity. This problem can be efficiently solved using the two-pointer technique, which ensures that we traverse the string only once, making the solution both optimal and easy to implement.

A palindrome is a word, phrase, or sequence that reads the same backward as forward, such as "madam", "racecar", or "A man, a plan, a canal, Panama". The problem here asks us to implement a function that checks whether a given string is a palindrome, ignoring non-alphanumeric characters and considering the string case-insensitively.

Problem Statement

Given a string s, return true if it is a valid palindrome (i.e., reads the same forward and backward), and return false otherwise.

Note:

• Only alphanumeric characters (letters and numbers) should be considered.
• The comparison should be case-insensitive.

Example 1:

go

Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: "A man, a plan, a canal: Panama" is a palindrome after removing non-alphanumeric characters and converting to lowercase.

Example 2:

go

Input: "race a car"
Output: false
Explanation: "race a car" is not a palindrome after removing non-alphanumeric characters.

Approach:

Two-Pointer Technique:

The optimal way to solve this problem is using the two-pointer technique. The idea is to use two pointers, one starting at the beginning (left) and the other starting at the end (right) of the string. We then:

1. Skip non-alphanumeric characters on both sides.
2. Compare the characters at the left and right pointers.
3. If the characters are not equal (case-insensitive), return false.
4. If they are equal, move the pointers inward and repeat the process.

Steps:

1. Initialize two pointers: one at the beginning of the string and one at the end.
2. While the left pointer is less than or equal to the right pointer:

• Skip over non-alphanumeric characters.
• Compare the characters at the left and right pointers, ensuring the comparison is case-insensitive.
• If they differ, return false.

1. If we finish the comparison without finding any mismatches, return true.

Go Implementation

Solution Using Two Pointers

go

package main

import (
    "fmt"
    "unicode"
)

// isPalindrome checks if the given string is a valid palindrome.
func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    
    for left < right {
        // Skip non-alphanumeric characters on the left side
        for left < right && !unicode.IsAlnum(rune(s[left])) {
            left++
        }
        
        // Skip non-alphanumeric characters on the right side
        for left < right && !unicode.IsAlnum(rune(s[right])) {
            right--
        }
        
        // Compare the characters at left and right, case-insensitive
        if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
            return false
        }
        
        left++
        right--
    }
    
    return true
}

func main() {
    // Test the isPalindrome function with some examples.
    fmt.Println(isPalindrome("A man, a plan, a canal: Panama")) // Output: true
    fmt.Println(isPalindrome("race a car"))                    // Output: false
    fmt.Println(isPalindrome(" "))                              // Output: true
    fmt.Println(isPalindrome("No 'x' in Nixon"))                // Output: true
}

Explanation:

1. Unicode Package:

• We use the unicode.IsAlnum() function to check if a character is alphanumeric (i.e., a letter or digit).
• We use unicode.ToLower() to convert the characters to lowercase to ensure the comparison is case-insensitive.

1. Two-Pointer Approach:

• The pointers left and right are initialized at the beginning and the end of the string, respectively.
• The for loop continues as long as the left pointer is less than or equal to the right pointer.
• Inside the loop, we skip any non-alphanumeric characters using two while loops.
• If the characters at the current left and right positions are not equal (case-insensitively), we return false.
• After comparing the characters, we move both pointers inward (left++ and right--) and continue checking.

1. Edge Case:

• The function handles cases with non-alphanumeric characters, spaces, and empty strings correctly.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Time Complexity:

• The time complexity is O(n), where n is the length of the string. We traverse the string once with two pointers, processing each character at most once.

Space Complexity:

• The space complexity is O(1). We use a constant amount of space, only storing a few pointers and variables.

Edge Cases

1. Edge Case: Empty String

• Input: ""
• Output: true
• Explanation: An empty string is trivially a palindrome since there’s nothing to compare.

1. Edge Case: String with Spaces and Punctuation

• Input: " , "
• Output: true
• Explanation: The spaces and punctuation are ignored, and the string is considered a palindrome.

1. Edge Case: Case-Insensitive Palindrome

• Input: "Aa"
• Output: true
• Explanation: The comparison is case-insensitive, so "Aa" is considered a palindrome.

1. Edge Case: Single Character String

• Input: "a"
• Output: true
• Explanation: A single character string is always a palindrome.

Conclusion

LeetCode 125: Valid Palindrome is a straightforward problem that involves checking whether a given string is a palindrome while ignoring spaces, punctuation, and case sensitivity. The solution, using the two-pointer technique, efficiently solves the problem in O(n) time, where n is the length of the string. The algorithm handles all edge cases, including empty strings, non-alphanumeric characters, and case differences, ensuring robustness.