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