Teaching Kids Programming – Different Algorithms to Check if a String is Palindrome

Teaching Kids Programming: Videos on Data Structures and Algorithms

What is a Palindrome string?

A Palindrome is a string that spelt backwards is also the same, like “racecar”.

Palindrome Algorithms

The basic idea is to reverse the string and check if it is the same.

def isPalindrome(s):
  return rev(s) == s

To reverse a string, we can do this:

def rev(s):
  ans = ""
  for i in s:
    ans = i + ans
  return ans

In Python, we can do this in one-liner:

def rev(s):
  return s[::-1]

We can also have two pointers pointing to begining and end of the string, compare both, and move towards the middle.

def isPalindrome(s):
  left, right = 0, len(s) - 1
  while left < right:
    if s[left] != s[right]:
       return False
    left += 1
    right -= 1
  return True

Using for, we can compute the corresponding index, and we just need to loop to middle index:

def isPalindrome(s):
  for i in range(len(s)):
    if s[i] != s[len(s) - 1 - i]:
      return False
  return True

Remember the data structure Stack – which is First In Last Out. We can convert the string into a list and use it as a stack – pop one element and check if the corresponding letter (from the begining) is the same:

def isPalindrome(s):
   arr = list(s):
   for i in s:
     x = arr.pop()
     if x != i:
       return False
   return True

–EOF (The Ultimate Computing & Technology Blog) —