[LeetCode] 100. Valid Palindrome (C#)

LeetCode - Problems - Algorithms - 100. Valid Palindrome

Valid Palindrome - LeetCode

My Solution (C#)

public class Solution {
    public bool IsPalindrome(string s) {

        if (string.IsNullOrWhiteSpace(s)) return true; //s is empty

        if (s.Length ==1 ) return true; //s has only one character


        int left = 0;   //start of input
        int right = s.Length - 1;   //end of input


        //if(s[left]==s[right]) //cannot check if it is alphanumeric


        while (left < right) //we are not middle of input
        {
            if(!char.IsLetterOrDigit(s[left]))
            {
                left++;
                continue;           // if not, just increase left. 
            }
            if(!char.IsLetterOrDigit(s[right]))
            {
                right--;
                continue;
            }

            char lc = char.ToLower(s[left++]);
            char rc = char.ToLower(s[right--]);

            if(lc != rc)
            {
                return false;
            }
        }
        return true;
    }
}

 

My Explanation

Okay... Let's discuss problem number 125 which is Valid Palindrome

Before we jump in to solve the problem, Palindrome is a phrase that reads the same forward and backward. 
For example


So, there are two conditions we need to do first.
all non-alphanumerical characters should be removed.
and all upper cases should be converted to lower cases.


First of all, we need to check the input s is null, thankfully with IsNullOrWhiteSpace method. If it says true, then return true. 

Then, we can check if the input s has only one character, then it also returns true.
(if it includes a non-alphanumeric character, it will be empty after removing it, so it means true!)

I'm going to make two variables one is for "left" which indicates the start of input and the other is "right" which indicates the end of input.

we need to check the first letter is the same as the last letter.
so I need to make an if statement "[left]th letter is same as [right]th?"

So I'm going to make a while loop that will repeat until 'left' is smaller than 'right'.

if those are not alphanumeric, let it get out of the loop. Non-alphanumeric characters will be skipped.

this is much more effective than removing all non-alphanumeric characters.

because we have to look at all the characters once to remove them.

and check if it is a palindrome. this method requires two times to look for one phrase to check if it is valid. time complexity 2O(n)

In this case, I mean, the way I'm solving requires only one time look to check it is valid. time complexity O(n)

After checking it is alphanumeric, I will assign char lc = char.ToLower(s[left++]);
char rc = char.ToLower(s[right--]);
and convert them to lowercases.
After conversion, left will be increased and right will be decreased.
now we can check lc and rc is same, 

this while loop will be repeated until the left is less than the right.
when the left is greater than the right, that means we checked until the exact center.

This script is written for the algorithm study group meeting.

Not confirmed professional just me who is still in junior level.