Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/8d3a1299fea09c35c0d2a475aa4b0ead to your computer and use it in GitHub Desktop.
Save jianminchen/8d3a1299fea09c35c0d2a475aa4b0ead to your computer and use it in GitHub Desktop.
Leetcode 125 - valid palindrome - code review - two pointers technique - filter once using O(n) time, and then check palindrome using O(n) time.
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());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment