DEV Community

Steven Frasica
Steven Frasica

Posted on

Solving the Palindrome Algorithm Problem

The journey of learning more algorithms continues, and with each problem, I'm gaining more experience with different approaches and patterns. It's always helpful to break down every algorithm into smaller steps to tackle. I think the palindrome problem is a good example of how to reach a solution in small steps.

Problem

We're provided with a string and we have to return true or false depending on whether or not the string is a palindrome. A palindrome is a word or string of letters that spells out the same word when reversed. In this problem, spaces and punctuation marks count as characters in the string too.

Ex.

palindrome("abba") === true
palindrome("abcdefg") === false
palindrome("racecar") === true

Approach

One way to solve this problem would be to convert the string into an array of characters and iterate through it to see if the sequence of characters are a palindrome. Essentially we'll be checking if the first element matches the last element, if the second element matches the second to last element, and so on.

Ex.

Our string is "racecar".
The array would be ['r', 'a', 'c', 'e', 'c', 'a', r']

Iterating through the array and checking pairs of characters as we move inwards from both ends of the array.

['r', 'a', 'c', 'e', 'c', 'a', 'r']

['r', 'a', 'c', 'e', 'c', 'a', 'r']

['r', 'a', 'c', 'e', 'c', 'a', 'r']

On the last step, both the left and right side will both meet at character 'e', so this is a palindrome.

Solution

function palindrome(string) {

}

//1.
Convert string to an array using the split method. Remember to put '' as the argument in the split method to split the word into individual characters.

function palindrome(string) {
  string.split('')
}

//2.
Use the .every() array method to check whether each character in the string matches up in the aforementioned way to determine if it's a palindrome. .every() will return a boolean based on the condition you pass into .every(). .every() takes in a function with two arguments, character and index.

function palindrome(string) {
  string.split('').every((character, index) => {
  //we will implement the condition here 
  }
}

Our condition is going to be checking pairs of elements starting from the left and right ends of the array and moving in.

function palindrome(string) {
  string.split('').every((character, index) => {
    character === string[string.length - index - 1]
  }
}

Remember to return on both lines to ensure our function outputs the answer we want, in this case a boolean.

function palindrome(string) {
  return string.split('').every((character, index) => {
    return character === string[string.length - index - 1]
  }
}

Let's break down what's inside the brackets after 'string'.
Arrays are zero-indexed so we need to subtract 1 from the string.length to get the last element in the array. Next, we subtract index from the string.length to move inwards to the array and match up with the element on the left side.

The palindrome problem has many approaches, as do all algorithm problems, and this is just one way to solve it. Regardless of what approach you use, it's always helpful to break down every problem to smaller steps. It helps to catch errors early on, and you build out a roadmap to the solution before writing down any code.

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Discussion (0)