Python Algorithm Q1

November 14, 2021

Q1 Valid Palindrome

Q

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.

Given a string s, return true if it is a palindrome, or false otherwise.

Sample Input

Input: s = “A man, a plan, a canal: Panama” Output: true Explanation: “amanaplanacanalpanama” is a palindrome.

Input: s = “race a car” Output: false Explanation: “raceacar” is not a palindrome.

Constraints

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Hints

pre-processing by filtering input. isalnum() is the method that checks whether object is (number or english) or not.

# this is the pre-processing function that made input regular lower-case english(or number).
arr = []
for char in arr:
    if char.isalnum(): #to check input 'char' is num&Eng or not, if true, return true. Vice versa.
        arr.append(char.lower()) #if true, append it to the list.

1. My Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        arr = []

        for char in s:
            if char.isalnum():
                arr.append(char.lower()) #loop for pre-processing

        a: int = 1
        cnt: int = 0

        for element in arr: #swipe array to check [0] == [-1], next [1]==[-2], ···
            if element == arr[-a]:
                cnt+=1
                a+=1

        if cnt == len(arr):
            return true
        else:
            return false
        
a = Solution() # create instance
a.isPalindrome("A man, a plan, a canal: Panama") #check array 's'

The most basic Soltuion. According to the book, takes 304 ms to execute.

2. Given Solution #1

Defining class ‘Solution’ will be skipped ‘cause it’s meaningless. Only the function “isPalindrome” will be written.

def isPalindrome(self, s: str) -> bool:
    strs=[]

    for char in s:
        if char.isalnum():
            strs.append(char.lower())


    #pop(x) returns xth element and deletes x. if none, returns the last element and deletes.
    #compare first & last, and then delete them. repeat until all gone.
    # return True if this passes all
    while len(strs)>1:
       if strs.pop(0)!=strs.pop(): 
           return False

    return True

3. Given Solution #2

Using type ‘Deque’ to improve the speed.

def isPalindrome(self, s: str) -> bool:
    #define strs by using the type 'Deque'  //deque is in the module "collections" (that's why we wrote 'collections.deque')
    strs: Deque = collections.deque()

    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs)>1:
       if strs.popleft()!=strs.pop(): 
           return False

    return True

Just using the type deque, performance highly improved. According to the book, takes 64 ms to execute. This is because in the type ‘list’, pop(0) is O(n). However, in the type ‘deque’, popleft() is O(1). Deque is ambidirectional Que, so you can add elements in both begin and last directions.

what is deque : https://velog.io/@rhdmstj17/자료구조-데크Deque-자료형이란

4. Given Solution #3

Using the slicing method, you can shorten the execution time.

def isPalindrome(self, s: str) -> bool:
    s = s.lower()
    s= re.sub('[^a-z0-9]','',s)
    return strs==strs[::-1] #just comparing string and reverse string.

Overall Review

Palindrome Validation checking is quite easy problem. But it can be solved in various ways. The solutions that the book provides is very interesting. I can decrease time-consuming works by just using the type ‘deque’. Also I don’t even think about string slicing. just writing the code ‘return s == s[::-1]’ can make the answer…

영어쓰기 1일차… 과연 언제까지 해낼 수 있을 것인가…

Hyuntae H