Palindrome

excerpt: This covers the basic building blocks Two Pointers Moving Towards Each Other and Linear Scan using While Loop.

Write a function that tests whether a string is a palindrome.

Iterative Implementation

The two pointers are initialized to the beginning and the end of the string for comparison of characters inside a while loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def palindrome?(s)
  i = 0
  j = s.size - 1
  
  while i < j
    if s[i] != s[j]
      return false
    end

    i += 1
    j -= 1
  end
  
  return true
end

One pointer can be used in combination with the relationship between the n and i to figure out the location of the right pointer without explicitly using a right pointer. In this case a for loop is used for traversing through the string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def palindrome?(s)
  n = s.size
  mid = n/2

  for i in (0..mid)
    if s[i] != s[n-1-i]
      return false
    end
  end

  return true
end

Recursive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def palindrome?(s, i , j)
  if i > j
    return true
  end

  if s[i] != s[j]
    return false
  end
  
  i += 1
  j -= 1
  
  palindrome?(s, i, j)    
end

s = 'racecar'
i = 0
j = s.size - 1

p palindrome?(s, i, j)

Compare the recursive version with the iterative version. The unit of work is done before the recursive call. The loop terminating condition is modified and becomes the base case.

Building Blocks

• Two Pointers Moving Towards Each Other
• Linear Scan using While Loop
• Unit of Work
• Terminating Condition in Loop and Base Case