Leetcode 125. Valid Palindrome (better performance?)

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 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:

enter image description here

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

• Phrancis: I would recommend you give it some time before posting a near-duplicate of your other question from just a bit earlier. Answers on this site take time and research to write, quite often.
• Phrancis: Great. Maybe start on another problem with what you've learned so far here, if you feel like it, and post that one when you're done with it :-)
• Willem van Rumpt: Tried it for fun: The timings provided by leetcode seem to be dodgy at best. Crafted a solution that beat 90.35% of the other solutions. Submitted exactly the same code again, and magically dropped to beating only 26.45% of the other solutions.
• Rick Davin: The Problem Statement begins with you should consider only alphanumeric characters. Based on that, an empty string should not be a palindrome since it does not contain any alphanumeric characters.
• mbomb007: @RickDavin For the purpose of this problem, we define empty string as valid palindrome.

Answer 1

The algorithm looks fine, but you have unconventional code, dead code, and verbose code.

Unconventional code

The C# convention is to use PascalCase (starting with uppercase) for function names.

Function-level documentation should be written in /// comments.

Dead code

fiterOutNonAlphanumbericaCharacters() 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 code

Defining 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 solution

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

• Jianmin Chen: Beautiful code, also, I learn to write for loop as you demo here. for (int start = 0, end = s.Length - 1; ; start++, end--) is a great fit with inside if statement checking start >= end. Unbelievable excellent engineering here!
• Jianmin Chen: I just give out a friendly reminder to add "return true" inside the function IsPalindrome as a last statement after the for loop.
• 200_success: There is no need to add a return true. Any statement after the for loop would be dead code, since the loop has no condition and no breaks. The only way to exit the loop is via the existing return true or return false.
• Jianmin Chen: I checked with Microsoft visual studio using your code. You are correct. That is new school for me.

Answer 2

Another possible version, making more use of the built in char methods

private bool IsPalindrome(string s)
{
 if (string.IsNullOrWhiteSpace(s)) return true;
 if (s.Length == 1) return true;
 var left = 0;
 var right = s.Length - 1;
 while (left < right)
 {
 if (!char.IsLetterOrDigit(s[left]))
 {
 left++;
 continue;
 }
 if (!char.IsLetterOrDigit(s[right]))
 {
 right--;
 continue;
 }
 var lhs = char.ToLower(s[left++]);
 var rhs = char.ToLower(s[right--]);
 if (lhs != rhs)
 {
 return false;
 }
 }
 return true;
}

Came out as 93%(ish) of csharp submissions

enter image description here

• paparazzo: Are you sure the { } balance? I would just skip the use of LHS and RHS variables.
• AlanT: It's a style thing. The compiler should optimize them out and it makes debugging a touch easier. The code is copied from a test class so I just tagged the bottom } of encapsulating class. Will fix
• Brian J: From the perspective of reviewing code, I would avoid using the increment/decrement operators during array access. It's only two more lines to keep them separate, and the intent is clearer (imo).

Answer 3

I like the accepted answer from 200_success +1

If you want to squeeze some more out of it then use a Dictionary<char, char>
Dictionary has O(1) lookup time

private static Dictionary<char, char> CharMap = new Dictionary<char, char>() {
 { '0', '0' }, { '1', '1' }, { '2', '2' }, { '3', '3' }, { '4', '4' }, { '5', '5' }, { '6', '6' }, { '7', '7' }, { '8', '8' }, { '9', '9' }
 , { 'A', 'A' }, { 'B', 'B' }, { 'C', 'C' }, { 'D', 'D' }, { 'E', 'E' }, { 'F', 'F' }, { 'G', 'G' }, { 'H', 'H' }, { 'I', 'I' }, { 'J', 'J' }, { 'K', 'K' }, { 'L', 'L' }, { 'M', 'M' }
 , { 'N', 'N' }, { 'O', 'O' }, { 'P', 'P' }, { 'Q', 'Q' }, { 'R', 'R' }, { 'S', 'S' }, { 'T', 'T' }, { 'U', 'U' }, { 'V', 'V' }, { 'W', 'W' }, { 'X', 'X' }, { 'Y', 'Y' }, { 'Z', 'Z' }
 , { 'a', 'A' }, { 'b', 'B' }, { 'c', 'C' }, { 'd', 'D' }, { 'e', 'E' }, { 'f', 'F' }, { 'g', 'G' }, { 'h', 'H' }, { 'i', 'I' }, { 'j', 'J' }, { 'k', 'K' }, { 'l', 'L' }, { 'm', 'M' }
 , { 'n', 'N' }, { 'o', 'O' }, { 'p', 'P' }, { 'q', 'Q' }, { 'r', 'R' }, { 's', 'S' }, { 't', 'T' }, { 'u', 'U' }, { 'v', 'V' }, { 'w', 'W' }, { 'x', 'X' }, { 'y', 'Y' }, { 'z', 'Z' }
 };
public static bool IsPalindrome(string s)
{
 for (int start = 0, end = s.Length - 1; ; start++, end--)
 {
 while (start < end && !CharMap.ContainsKey(s[start]))
 {
 start++;
 }
 while (start < end && !CharMap.ContainsKey(s[end]))
 {
 end--;
 }
 if (start >= end)
 {
 return true;
 }
 if (CharMap[s[start]] != CharMap[s[end]])
 {
 return false;
 }
 }
}

• mbomb007: Using a dictionary was a great idea! Do you know what percentage this solution gets?
• paparazzo: @mbomb007 I don't have a Leet account.
• Corak: This is indeed a good idea, but sadly it seems like the total time to access the dictionary is still higher than the IsAlphanumeric check and the ToUpper from the solution of 200_success combined. (at least on my machine)
• paparazzo: @Corak Wow, I did not test but I thought this would be much faster.
• Corak: Nope, I even tried an alteration where I stored the value from CharMap (to reduce key lookup time). Basically char startChar; while(start < end && !CharMap.TryGet(s[start], out startChar)) and then if (startChar != endChar). This came even closer to 200_success, but still didn't beat it.