Ruby Algorithm Series #3: Palindrome Check Problem in Ruby A Complete Guide with Validation and TDD/BDD Testing

Concept of a Palindrome

A palindrome is a string that reads the same forward and backward, ignoring cases, spaces, and special characters. For example:

• “madam” → Palindrome
• “racecar” → Palindrome
• “hello” → Not a palindrome

How to Analyze the Problem

1. Understand the Problem:
   • A string is considered a palindrome if the sequence of characters is identical when reversed.
   • Ignore cases and non-alphanumeric characters (optional based on requirements).
2. Break Down Requirements:
   • Input: A string.
   • Output: Boolean (true if palindrome, false otherwise).
3. Plan Validation:
   • Ensure the input is a string.
   • Handle edge cases like empty strings or non-alphanumeric inputs.
4. Think About the Solution:
   • Reverse the string and compare it to the original.
   • Alternatively, use two pointers to check characters from both ends.
5. Dry Run: For "madam":
   • Start: Compare ‘m’ (index 0) with ‘m’ (index -1).
   • Next: Compare ‘a’ (index 1) with ‘a’ (index -2).
   • Middle reached: Palindrome confirmed.

Algorithm

1. Input Validation:
   • Check if the input is a valid string.
   • Return false for invalid inputs.
2. Normalize the String:
   • Convert to lowercase.
   • Remove non-alphanumeric characters (if required).
3. Palindrome Check:
   • Use two methods:
     • Reverse the string and compare.
     • Use two pointers (one at the start, one at the end) to compare characters iteratively.
4. Output:
   • Return true if the string is a palindrome, false otherwise.

# Palindrome Check Implementation
class PalindromeChecker
  # Method to check if a string is a palindrome
  def self.palindrome?(input)
    validate_input(input) # Validate input

    # Normalize the string
    normalized = input.downcase.gsub(/[^a-z0-9]/, '')

    # Check for palindrome using two-pointer technique
    left = 0
    right = normalized.length - 1

    while left < right
      return false if normalized[left] != normalized[right]
      left += 1
      right -= 1
    end

    true
  end

  private

  # Input validation to ensure it is a string
  def self.validate_input(input)
    raise ArgumentError, "Input must be a valid string." unless input.is_a?(String)
  end
end

# Example Usage
if __FILE__ == $0
  input_string = "A man, a plan, a canal, Panama"
  puts "Input String: '#{input_string}'"
  puts "Is Palindrome? #{PalindromeChecker.palindrome?(input_string)}"

  # Test Cases
  require 'rspec/autorun'

  RSpec.describe PalindromeChecker do
    describe '.palindrome?' do
      context 'when input is a valid palindrome' do
        it 'returns true for a simple palindrome' do
          expect(PalindromeChecker.palindrome?("madam")).to eq(true)
        end

        it 'returns true for a palindrome with spaces and punctuation' do
          expect(PalindromeChecker.palindrome?("A man, a plan, a canal, Panama")).to eq(true)
        end

        it 'returns true for a single character' do
          expect(PalindromeChecker.palindrome?("a")).to eq(true)
        end
      end

      context 'when input is not a palindrome' do
        it 'returns false for a non-palindrome string' do
          expect(PalindromeChecker.palindrome?("hello")).to eq(false)
        end

        it 'returns false for an empty string' do
          expect(PalindromeChecker.palindrome?("")).to eq(false)
        end
      end

      context 'when input is invalid' do
        it 'raises an error for non-string input' do
          expect { PalindromeChecker.palindrome?(12345) }.to raise_error(ArgumentError, "Input must be a valid string.")
        end
      end
    end
  end
end

Run this Code

Save the Ruby code in a file named PalindromeChecker.rb and execute it using the command: ruby PalindromeChecker.rb.

How to Think About Solutions

1. Start by understanding the requirements:
   • Does the solution need to ignore spaces, case, or special characters?
   • Is efficiency a concern?
2. Divide the task:
   • Normalize the input (if required).
   • Use a method (like reversing or two-pointer traversal) to check for palindrome properties.
3. Test edge cases and invalid inputs:
   • Handle empty strings, single characters, and non-alphanumeric inputs.
4. Optimize:
   • Use a two-pointer technique for linear-time palindrome checks.