Problem statementGiven a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example,A man, a plan, a canal: Panama is a palindrome.race a car is not a palindrome.Note:Have you consider that the string might be empty? This is a good question to ask during an interview.For the purpose of this problem, we define empty string as valid palindrome.Introduction of algorithmThe current implementation beats 87% C# submission, runtime: 112 ms, my last practice only beats 25.59% C# submission. I also value the good performance result and this practice just accidentally showed me a possible good design. I enjoyed the practice because I ran into time out-of-index error, so I put some defensive checking of index-out-of-range 3 times, the first one is begin < end in first nested while loop, the 2nd, 3rd checkings are added without hesitation. In detail, 2nd is end >= 0 in the second nested while loop, 3rd is if(start >= end) after the nested two while loops. And surprisingly the performance is much better than the one filtering nonalphanumeric characters first using O(N) time (N is the string's length). I am open to the advice of performance, coding guidelines, nested while, defensive checking etc. I did some study in June 2016 about coding strategies, because I failed my first practice of Leetcode 125, I got so many options, use while/if, nested while, or flat code. I did not have a good understanding what is important. At the beginning, I say no to nested while loop, try to make the code more flat to left side, since I studied cyclomatic complexity and learn to lower the  cyclomatic complexity of the function.   Please take a look the performance of this practice:The C# code passes leetcode online judge.  using System;using System.Collections.Generic;using System.Diagnostics;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Leetcode125_IsPalindrome{    class ValidPalindrome    {        /*         *  Leetcode 125: Valid Palindrome         *  https://leetcode.com/problems/valid-palindrome/?tab=Description         */        static void Main(string[] args)        {            RunTestcases();        }        public static void RunTestcases()        {            Debug.Assert(IsPalindrome(Aa));            Debug.Assert(IsPalindrome(Ab%Ba));            Debug.Assert(IsPalindrome(B%1*1b));            Debug.Assert(!IsPalindrome(B%a*1b));        }        /*          * Given a string, determine if it is a palindrom, considering         * only alphanumeric characters and ignoring cases         * Time complexity:          * O(N)         *           * empty string is valid palindrome          */        public static bool IsPalindrome(string rawString)        {            if (rawString == null || rawString.Length == 0)            {                return true;            }            // two pointers techniques             int start = 0;            int end = rawString.Length - 1;            while (start < end )               {                               while (start < end && !isAlphabeticAndDigit(rawString[start]))                {                    start++;                }                while (end >= 0 && !isAlphabeticAndDigit(rawString[end]))                {                    end--;                }                               if(start >= end)                {                    return true;                 }                char left  = rawString[start];                char right = rawString[end];                if (toUpper(left) != toUpper(right))                {                    return false;                }                start++;                end--;                            }            return true;        }        /*         * check if the char is alphabetic or digit         * a-z         * A-Z         * 0-9         */        private static bool isAlphabeticAndDigit(char anyChar)        {            if (isCapitalCaseAlphabetic(anyChar) ||               isLowerCaseAlphabetic(anyChar) ||               isDigit(anyChar))            {                return true;            }            return false;        }        private static bool isCapitalCaseAlphabetic(char anyChar)        {            var number = anyChar - 'A';            return number >= 0 && number < 26;        }        private static bool isLowerCaseAlphabetic(char anyChar)        {            var number = anyChar - 'a';            return number >= 0 && number < 26;        }        private static bool isDigit(char anyChar)        {            var number = anyChar - '0';            return number >= 0 && number <= 9;        }        /*         * assuming input char is alphabetic number,          * output the capitical case char         */        private static char toUpper(char alphabeticChar)        {            int number = alphabeticChar - 'a';            if (number >= 0 && number < 26)            {                return (char)('A' + number);            }            return alphabeticChar;        }        /*         * Filter out non alphanumeric characters         * and keep cases         */        private static string fiterOutNonAlphanumbericaCharacters(string rawString)        {            return string.Concat(rawString.Where(c => isAlphabeticAndDigit(c) == true).ToArray());        }    }}
Leetcode 125. Valid Palindrome (better performance?)
c#;performance;algorithm;programming challenge;palindrome
The algorithm looks fine, but you have unconventional code, dead code, and verbose code.Unconventional codeThe C# convention is to use PascalCase (starting with uppercase) for function names.Function-level documentation should be written in /// comments.Dead codefiterOutNonAlphanumbericaCharacters() is unused.  It is also misspelled, by the way.  AlphanumericFilter(string s) would have been a better name, if you had needed such a function.The following namespaces are unused:using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;Verbose codeDefining isAlphabeticAndDigit(), isCapitalCaseAlphabetic(), isLowerCaseAlphabetic(), and isDigit() is overkill.  All you really care about is one IsAlphanumeric() function.  And you can implement it without arithmetic  just do some comparisons.  (You could use System.Char.IsLetterOrDigit(), but that function is Unicode-aware, and may be more complicated than what you need.)In IsPalindrome(), the rawString.Length == 0 special case is unnecessary, and wouldn't help improve performance by any noticeable amount.  You should drop useless special cases, since they clutter up the code and prevent you from demonstrating that the general-case code also works for degenerate cases.  For that matter, I would drop the rawString == null check as well, since it is philosophically debatable whether the absence of a string constitutes a palindrome.The main loop in IsPalindrome() would be better written as a while (true) loop, as the while (start < end) condition is redundant.  In fact, I would rewrite it as a for loop, both for compactness and readability.Parameter names can be shortened (anyChar c, and rawString s).Suggested solutionusing System;using System.Diagnostics;namespace Leetcode125_IsPalindrome{    /// <summary>    /// Leetcode 125: Valid Palindrome    /// https://leetcode.com/problems/valid-palindrome/?tab=Description    /// </summary>    class ValidPalindrome    {        static void Main(string[] args)        {            Debug.Assert(IsPalindrome(Aa));            Debug.Assert(IsPalindrome(Ab %Ba));            Debug.Assert(IsPalindrome(B%1*1b));            Debug.Assert(!IsPalindrome(B%a*1b));        }        /// <summary>         /// Given a string, determine if it is a palindrome, considering        /// only alphanumeric characters and ignoring case.        /// </summary>        public static bool IsPalindrome(string s)        {            for (int start = 0, end = s.Length - 1; ; start++, end--)            {                while (start < end && !IsAlphanumeric(s[start]))                {                    start++;                }                while (start < end && !IsAlphanumeric(s[end]))                {                    end--;                }                               if (start >= end)                {                    return true;                 }                if (ToUpper(s[start]) != ToUpper(s[end]))                {                    return false;                }                          }        }        /// <summary>        /// Check if the char is in one of the ranges A-Z, a-z, or 0-9.        /// <summary>        private static bool IsAlphanumeric(char c)        {            return (('A' <= c && c <= 'Z') ||                    ('a' <= c && c <= 'z') ||                    ('0' <= c && c <= '9'));        }        /// <summary>        /// If character is lowercase, convert it to uppercase        /// </summary>        private static char ToUpper(char c)        {            return ('a' <= c && c <= 'z') ? (char)(c - 'a' + 'A') : c;        }    }}