Palindrome Algorithm

Given that a palindrome is a string that is identical when reversed (e.g. “evil rats on no star live”), I have made the following assumptions:

  1. The input string will be greater than two characters in length (i.e. 3 or more) to allow only true palindromes
  2. The input string can consist of any character, however only those representing lower / upper case alphabet letters or numbers can be considered
  3. All upper case letters will be converted to lower case for comparison
  4. Any letters approximating to other letters (accents, umlauts, cedillas, etc.) are replaced by their non approximated lower case alphabetic companion for comparison (e.g. é will be replaced by e, ç by c, ñ by n, ö by o, etc.)
  5. All punctuation and spaces will be removed for comparison
  6. The input string does not have to be verified as a collection of dictionary words or valid in any other way
  7. For algorithm efficiency it is only necessary to compare either half of the characters (in an even length modified input string) or half the characters minus 0.5 (in an odd length modified input string) to determine if a palindrome exists

Therefore an algorithm to process any string and decide if it is a palindrome, for effectiveness, would be better to look for a false result and end immediately as follows:

procedure Palindrome
do (remove spaces and punctuation from string)
do (replace any approximated characters with standard alphabet characters from string (assumption 4 above))
do (let result = 0)
if (modified input string is less than 3) then (result = false “Not a palindrome” and exit)
do (let ‘n’ = the number of characters)
do (put each character into a queue)
do (put each character into a stack)
do (let i = 0)
while (1 to (rounddown(n/2)))
do (compare the character in position [i] in the queue and the stack)
if (queue[i+1] is the same as stack[n-i]) then (let i = i + 1) else (result = false “Not a palindrome” and exit)
end while
result = true “A palindrome” and exit
end procedure

As you can see from the algorithm above I used a queue (list) for the original modified input string so that a First-In-First-Out (FIFO) method could be used to examine the string and a stack (list) data structure for the second comparison (reversal necessary) as these are ideal for storing items that must be retrieved in the reverse order from which they were stored due to their Last-In-First-Out (LIFO) structure (Glenn Glenn Brookshear, J. 2009). I elected not to use a list as it would have meant that the algorithm would have been more complex (and hence not as efficient) due to having to select characters from the list based on mathematical placing rather than next/previous steps. Finally I chose not to use a tree data structure as a palindrome does not have a hierarchical structure and as such it would not have been possible, without further extraction, to perform the necessary character comparisons.

For those with Perl programming knowledge, there exists a routine to examine palindromic strings = (substr($str,0,length($str)/2) eq reverse(substr($str,-length($str)/2))).

References

Glenn Brookshear, J. (2009) Computer Science: An Overview. 10th ed. Boston: Pearson Education.