2
\$\begingroup\$

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?

\$\endgroup\$

migrated from softwareengineering.stackexchange.com Nov 28 '16 at 18:59

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ Is there a reason you don't just reverse the string, then check if they're equal? \$\endgroup\$ – TZHX Nov 26 '16 at 21:17
  • \$\begingroup\$ @TZHX My only reason for not using reverse is that in the interview it was prohibited and I've tried to write it without using .Reverse() as well. \$\endgroup\$ – nick gowdy Nov 26 '16 at 21:34
  • 1
    \$\begingroup\$ Ah, yes... got to love arbitrary restrictions. Well, if I were tasked with that, I'd consider that your solution approaches N^2 operations for a palindrome (scaling quite badly with size of the string). I can suggest a way it might be done only looping through the input once, but it's been a long day and I don't have the energy to check for edge cases. \$\endgroup\$ – TZHX Nov 26 '16 at 21:43
6
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ +1, but I think you should return true rather than false for the empty string. Also, i <= chars.Length / 2 can safely be changed to i < chars.Length / 2. (That will also let you eliminate the specific check for the empty string.) \$\endgroup\$ – ruakh Nov 27 '16 at 1:06
  • 1
    \$\begingroup\$ You don't actually even need to call .ToCharArray(). Strings are naturally indexable in C#. \$\endgroup\$ – KChaloux Nov 28 '16 at 15:07
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.