Leetcode #125 Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        // Change input string to lower case
        s = s.lower()
        target = ""
        
        for el in s:
        	// trim input string to just have alphabet and numeric types
            if el.isalnum():
                target = target + el
                
        // When target String is 0 or have only one letter returns true immediately
        if len(target) == 0 or len(target) == 1:
            return True
		
        // find middle point that 2 pointers can meet
        myrange = len(target) / 2
        
        // loop one from the head and other from the tail
        for i in range(myrange):
        	// when there is no matching return flase
            if target[i] != target[(-1-i)]:
                return False
        else:
            return True

This works fine however, because I have to delcare a new string to hold trimmed and use loop, it takes some extra memeory spaces and loop that is not nesessary. 

 

 

class Solution:
    def isPalindrome(self, s: str) -> bool:
    
    	// Set left pointer to head and right pointer to tail.
        l, r = 0, len(s) - 1
        
        // so when left pointer is still left than right meaning they are far enough
        // we loop
        while l < r:
        	
            // when l is still left than right pointer and character of s[l] is not alphabet or numeric.
            // increase the head index
            
            ** have to use while incase of this kinds of input
            ** "....acca..........(()"
            while l < r and not isalnum(s[l]):
                l += 1
            
            // when r is still right than left pointer and character of s[r] is not aphabet or numeric.
            // decrease the tail index
            while l < r and not isalnum(s[r]):
                r -= 1
                
            // and now compare the 2 strings.
            if s[l].lower() != s[r].lower():
                return False
                
            // increase and decrease both head and tail index
            l += 1
            r -= 1
        return True

Now it gets way faster and better memory useage.

 

In additionally there is a built in function that makes it easy if we don't have to worry about space and speed

 

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        newstr = ""
        for i in s:
            if i.isalnum():
                newstr += i.lower()
        return newstr == newstr[::-1]

 

This is something call extended slices. Examples are better than word so here it is.

 

For example, you can now easily extract the elements of a list that have even indexes:

>>> L = range(10)
>>> L[::2]
[0, 2, 4, 6, 8]

Negative values also work to make a copy of the same list in reverse order:

>>> L[::-1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]