Palindrom Check

A word is palindrom if you can read it same backwards and forwards. For example madam or abba.

To check for palindrom we have 2 ways to do it.

From side to middle

We can check if the character of the sides are the same going into the middle. For example:

abba       a == a
^  ^

abba       b == b
 ^^

So "abba" is palindrom

madam      m == m
^   ^

madam      a == a
 ^ ^

  
madam      We ignore `d` if it's odd as not important
  ^

So "madam" is palindrom

Implementation

class App:
    def checkSideToMid(self, string: str) -> bool:
        if not string: return True

        left, right = 0, len(string) - 1

        while left < right: 
            if string[left] != string[right]:
                return False
            
            left += 1
            right -= 1
        
        return True

Time complexity: $O(n)$
Space complexity: $O(1)$

From middle to side

We can also check if the string is anagram from middle to side, for example:

abba       b == b
 ^^

abba       a == a
^  ^

So "abba" is palindrom

madam      We ignore `d` if odd as not important
  ^ 

madam      a == a
 ^ ^

madam      m == m
^   ^

So "madam" is palindrom

Implementation

class App:
	def checkMidToSide(self, string: str) -> bool:
        if not string: return True
        
        evenString = len(string) % 2 == 0
        mid = len(string) // 2

        left = mid - 1
        right = mid if evenString else mid + 1

        while left >= 0 and right < len(string):
            if string[left] != string[right]: 
                return False

            left -= 1
            right += 1
        
        return True

Time complexity: $O(n)$
Space complexity: $O(1)$