Leetcode 125. Valid Palindrome

Question

Problem statement

Given 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 algorithm

The implementation of the algorithm is to scan the string once from left to right to filter out non-alphanumeric characters first, and then check the string is valid palindrome ignoring cases. The reason I like the implementation is that the code has some simplicity, avoid mixing checking if it is alphanumeric character with two pointers techniques.

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;
            }

            string stringWithCases = fiterOutNonAlphanumbericaCharacters(rawString);

            // two pointers technique
            int start = 0;
            int end = stringWithCases.Length - 1;

            while (start < end)
            {
                char left  = toUpper(stringWithCases[start]);
                char right = toUpper(stringWithCases[end]);

                if (left - right != 0)
                {
                    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());            
        }
    }
}

Answer 1

Seems to me that creating stringWithCases is overhead you don't need compared to just skipping characters and process the actual string.

If you are going to create stringWithCases then why not create stringWithOutCases? isLowerCaseAlphabetic could do the conversion cheaply.