Palindromes in C# - CodeProject

Introduction

This code calculates if a string is a palindrome, and was inspired by the Channel9 video by Gary Daniels and Evan Goldring - Mock whiteboard problem.

Background

There are two main approaches to calculating palindromes: byte symmetry, or on the basis of words. Byte symmetry checks to see if a string is a mirror image of itself "helloolleh", whilst the other approach handles white spaces "Was it Eliot's toilet I saw?"

Using the code

I've not inluded the code as an attachment, rather as inline text that can be used directly.

static bool isPalindrome(string subject)
{
  const int STEP_FORWARD = 1;
  const int STEP_BACKWARD = -STEP_FORWARD;
  const int BEFORE_START = -1;
  const int CHAR_AT_A_TIME = 1;
  const int COMPARE_EQUALS = 0;

  // assume its not a palindrome
  bool result = false;

  // how to compare
  CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
  CompareOptions co =
    CompareOptions.IgnoreCase |
    CompareOptions.IgnoreKanaType |
    CompareOptions.IgnoreNonSpace |
    CompareOptions.IgnoreSymbols |
    CompareOptions.IgnoreWidth; |

  // null strings are not palindromes
  if (subject != null)
  {
    int AFTER_END = subject.Length;

    // single letter words are palindromes
    result = (AFTER_END == 1 && IsPalindromeChar(subject[0]));

    // start the comparison points at valid characters
    int startOffset = GetNextValidCharacter(subject, BEFORE_START, 
                                         STEP_FORWARD, AFTER_END);
    int endOffset = GetNextValidCharacter(subject, AFTER_END, 
                                STEP_BACKWARD, BEFORE_START);

    while (startOffset < endOffset)
    {
      result = ci.Compare(subject, startOffset, CHAR_AT_A_TIME, 
               subject, endOffset, CHAR_AT_A_TIME, co) == COMPARE_EQUALS;
  
      if (!result)
        break;

      // move the comparison points towards each other
      startOffset = GetNextValidCharacter(subject, startOffset, 
                                      STEP_FORWARD, endOffset);
      endOffset = GetNextValidCharacter(subject, endOffset, 
                               STEP_BACKWARD, startOffset);
    }
  }

  return result;
}

static int GetNextValidCharacter(string subject, int offset, 
                                 int step, int bound)
{
  if (offset != bound)
    offset += step;

  while (offset != bound && !IsPalindromeChar(subject[offset]))
    offset += step;

  return offset;
}   

static bool IsPalindromeChar(char c)
{
  return char.IsLetter(c) || char.IsDigit(c);
}

Points of interest

Reading the Wikipedia entry on palindromes shows that there are more than just alphabetical palindromes, so it is worth checking with your users before assuming that this code is what they mean by a palindrome.

On my blog, I've also included the byte symmetry code approach.

History

Aug/2008 - First version.

You must Sign In to use this message board.


Per page

on the basis of words?
PIEBALDconsult

12:42 29 Aug '08

I thought the "on the basis of words" type was "fall leaves after leaves fall".
Sign In·View Thread·PermaLink

Re: on the basis of words?
Philip Fitzsimons

1:29 30 Aug '08

that kind of highlights the whole issue - the solution of palindromes is very much dependant on what you want to accept as a palindrome... hopefulyy the article solves most kinds of plaindromes, and gives a starting point for all the others... "When the only tool you have is a hammer, a sore thumb you will have."
Sign In·View Thread·PermaLink

Another approach
Ravi Bhavnani

10:26 28 Aug '08

I believe this may accomplish the same result:

  bool IsPalindrome
      (string theString)
  {
       Collection<char> charsLR = new Collection<char>();
       Collection<char> charsRL = new Collection<char>();
       for (int index=0; (index < theString.Length); index++) {
            if (Char.IsLetter (theString[index])) {
                charsLR.Add (theString[index]);
                charsRL.Insert (0, theString[index]);
            }
       }
       return charsLR.Equals (charsRL);
  }

/ravi

My new year resolution: 2048 x 1536
Home | Articles | My .NET bits | Freeware
ravib(at)ravib(dot)com

Re: Another approach
PIEBALDconsult

10:46 28 Aug '08

Better to have short-circuit failure -- return false as soon as you can, without processing further characters.
Sign In·View Thread·PermaLink

Re: Another approach
Ravi Bhavnani

10:48 28 Aug '08

Wouldn't that require 2 passes? /ravi My new year resolution: 2048 x 1536 Home \| Articles \| My .NET bits \| Freeware ravib(at)ravib(dot)com
Sign In·View Thread·PermaLink

Re: Another approach
PIEBALDconsult

11:26 28 Aug '08

No.
Sign In·View Thread·PermaLink

Re: Another approach
Ravi Bhavnani

11:30 28 Aug '08

Sorry, I guess what I meant was 2 indexed access into the string (one L to R, the other R to L). My method only does a single access into the source string (at the expense of walking the entire string).

(To whoever 1-voted my note):
I'm not suggesting it's optimal; I was only offering an alternative.

/ravi

My new year resolution: 2048 x 1536
Home | Articles | My .NET bits | Freeware
ravib(at)ravib(dot)com

Re: Another approach
PIEBALDconsult

11:46 28 Aug '08

Ravi Bhavnani wrote:
(one L to R, the other R to L).

They both stop at the center of the string.

With your solution you traverse the entire string, and then the Equal will traverse it at least partway, perhaps the whole way.

With the solution presented (and mine*, and others) we traverse the string at most once (or halfway twice if you like).

In some cases we'll only compare the first and last characters.

* Actually, my Purify method will also the traverse the string as well, whereas the solution presented won't.

Re: Another approach
Ravi Bhavnani

11:49 28 Aug '08

Got it - thanks. /ravi My new year resolution: 2048 x 1536 Home \| Articles \| My .NET bits \| Freeware ravib(at)ravib(dot)com
Sign In·View Thread·PermaLink

Re: Another approach
Philip Fitzsimons

0:48 29 Aug '08

you would only need to go halfway: `for (int index=0; (index < theString.Length / 2); index++)` "When the only tool you have is a hammer, a sore thumb you will have."
Sign In·View Thread·PermaLink

Re: Another approach
Ravi Bhavnani

4:45 29 Aug '08

True, and the compare would check the characters at `[index]` and the `[length-index]`, with consideration being made for the odd number length case. /ravi My new year resolution: 2048 x 1536 Home \| Articles \| My .NET bits \| Freeware ravib(at)ravib(dot)com
Sign In·View Thread·PermaLink

Re: Another approach
Jared Mcguire

10:21 29 Aug '08

I happened to have this sitting in my personal library:

Private Function TestPalindrome(ByVal Text As String, _
 ByVal IgnoreCase As Boolean, _
 ByVal IgnoreWhitespace As Boolean, _
 ByVal IgnorePunctuation As Boolean) As Boolean

	'Ignore case?
	If IgnoreCase Then Text = Text.ToLower

	'Ignore whitespace?
	If IgnoreWhitespace Then Text = Regex.Replace(Text, "\s", String.Empty)

	'Ignore punctuation.
	Text = Regex.Replace(Text, "[^\w\s]", String.Empty)

	'Convert to a character array.
	Dim TextChar() As Char = Text.ToCharArray

	'Compare the first character with the last character and move inward, meeting at
	'the middle. For odd lengths the center character is ignored.
	For Index As Integer = 0 To TextChar.Length / 2 - 1
		'Return false if a non match is found
		If TextChar(Index) <> TextChar(TextChar.Length - Index - 1) Then Return False
	Next

	'No inequalities were found.
	Return True
End Function

Re: Another approach
PIEBALDconsult

12:19 29 Aug '08

Wow, that's a lot of traversals of the string. 1) ToLower 2) Remove whitespace 3) Remove punctuation 4) Convert to array -- which isn't even necessary 5) And finally across the array You could also use string.Replace rather than Regex.Replace And I suspect it otherwise works like mine... throws an Exception if the string is null and returns true if it's empty.
Sign In·View Thread·PermaLink

Oh goody
PIEBALDconsult

7:35 28 Aug '08

A reason to review my palindrome checking method (looks like I wrote it four years ago).

Mine is simplified by the use of my Purify method which, in this usage, removes any characters that I want to ignore.


public static bool
IsPalindrome
(
    string subject
)
{
    return ( IsPalindrome ( subject , "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ) ) ;
}
 
public static bool
IsPalindrome
(
    string subject 
,
    string goods
)
{
    bool result = true ;
 
    subject = PIEBALD.Lib.LibStr.Purify ( subject.ToUpper() , goods , null , null , null ) ;
 
    for ( int runner = 0 ; runner < subject.Length/2 && result ; runner++ )
    {
        result = subject [ runner ] == subject [ subject.Length - 1 - runner ] ;
    }
 
    return ( result ) ;
}

Hmmm... I think I can change it to a while loop and use a HashSet to contain the desired characters...

Re: Oh goody
Philip Fitzsimons

0:43 29 Aug '08

nice! though your comparasion does assume an exact match... "When the only tool you have is a hammer, a sore thumb you will have."
Sign In·View Thread·PermaLink

Re: Oh goody
PIEBALDconsult

5:22 29 Aug '08

Note the cleverly hidden ToUpper.
Sign In·View Thread·PermaLink

Re: Oh goody
Philip Fitzsimons

6:12 29 Aug '08

oh, I saw that I meant in the case of: "A man, a plan, a canal - Panamá!" "When the only tool you have is a hammer, a sore thumb you will have."
Sign In·View Thread·PermaLink

Re: Oh goody [modified]
PIEBALDconsult

11:28 29 Aug '08

Oh, right, well inspired by your article I spent all day yesterday reworking mine. Thank you very little.

But because some Unicode glyphs require more than one character, a fully-Unicode-compliant palindrome detector may be even more difficult than I thought and I'm trying very hard not to work on it today... maybe all weekend though. Unsure

P.S. I just tested what I did yesterday and it properly handles "A man, a plan, a canal - Panamá!" when I specify that the HashSet<char> is to use the InvariantCulture, IgnoreNonSpace, and IgnoreCase.

P.P.S. I just tested my current version with the Hebrew and Greek examples from the Wikipedia page; the Hebrew and Medieval Greek examples returned true, the Modern Greek example (with psi) returned false.

D'Oh!

I had forgotten to ignore whitespace -- the Modern Greek returns true.

modified on Friday, August 29, 2008 6:12 PM

Re: Oh goody
Philip Fitzsimons

1:27 30 Aug '08

opps sorry, did not mean to cause you so much work! "When the only tool you have is a hammer, a sore thumb you will have."
Sign In·View Thread·PermaLink

Re: Oh goody
PIEBALDconsult

8:58 30 Aug '08

It's alright, if I didn't enjoy programming I'd be doing something else.

Anyway, I spent last evening writing a struct which contains a string to hold either a single char or a surrogate pair, and a comparer to work with them, then reworked my IsPalindrome methods to use the new struct. I have tested it with the examples mentioned and it works, but I still need to test it with surrogate pairs (if I can find some). I'm also doing more reading up on Unicode to see what else I may have missed.

Introduction

Background

Using the code

Points of interest

History

"When the only tool you have is a hammer, a sore thumb you will have."

"When the only tool you have is a hammer, a sore thumb you will have."

"When the only tool you have is a hammer, a sore thumb you will have."

"When the only tool you have is a hammer, a sore thumb you will have."

"When the only tool you have is a hammer, a sore thumb you will have."