Palindrome algorithm in C#

Question

I had an interview yesterday where I had to write an algorithm on the whiteboard for working out if a value is a Palindrome in C#. The pressure got to me a bit but I've written my version of it in Visual Studio this evening.

 private bool Ispalindrome(string args)
        {
            var index = 0;
            var reverseArray = args.ToCharArray();

            do
            {
                if(index == args.Length)
                    return true;

                index++;
                var startingChars = args.Substring(0, index);
                var stringbuilder = new StringBuilder();

                for (var i = 0; i < index; i++)
                {
                    stringbuilder.Append(reverseArray[reverseArray.Length-i-1]);
                }

                if (startingChars != stringbuilder.ToString())
                    _isPalindrone = false;

            } while (_isPalindrone);
            return _isPalindrone;
        }

Doe anyone have any recommendations on how to make this more efficient?

Answer 1

You are making it harder than it needs to be.

You just need to compare one character at a time:

private static bool IsPalindrome(string s)
{
    if (string.IsNullOrEmpty(s))
        return false;
    char[] chars = s.ToLower().ToCharArray();
    for (int i = 0; i < chars.Length / 2; i++)
        if (chars[i] != chars[chars.Length - 1 - i])
            return false;
    return true;
}

Or:

private static bool IsPalindrome(string s)
{
    if (string.IsNullOrEmpty(s))
        return false;
    char[] chars = s.ToLower().ToCharArray();
    for (int i = 0, j = chars.Length - 1 ; i < j; i++, j--)
        if (chars[i] != chars[j])
            return false;
    return true;
}

Answer 2

How about this in pseudocode:

front = 0
back = str.len() - 1
isPalindrome = true;
while (front < back) {
   If str[front] != str[back] {
     isPalindrome = false;
     break;
   }
   ++front;
   --back;
}
return isPalindrome

This doesn't need a new structure, and only access at most \$n+1\$ characters on the string, so it's \$O(n)\$. This would probably work for most Latin character sets. Two character symbols would throw this off track.

Answer 3

Consider that for the majority of strings, the first character is not the same as the last character. And the string is not a palindrome for that reason. I'd expect an algorithm that runs in constant time for most strings. And in linear time for strings that are palindromes.

It would also be nice to handle Unicode correctly. At the very least strings with four byte characters need to be handled correctly. But really strings containing characters with modifiers, and such characters in non-canonical form, should be handled correctly as well.