Created
March 10, 2017 05:06
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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