Data Structures and Algorithms

Challenge 1: Checking for a Palindrome

A data structure is?a named location that can be used to store and organize data. An algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allow us to write efficient and optimized computer programs. I am starting a new 30-day challenge where we tackle some problems using algorithms as well as looking at the most efficient solution possible using Big O notation. ?Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. To understand more about Big O notation you can read this article which will explain in detail.

I will be using Javascript for most of the solutions but you can use any language of your choice to solve these problems. So let's begin!

Question: Given a string?s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

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

Given the instructions from the problem, we are given a string we have to determine if it is a palindrome considering only alphanumeric characters, ignoring cases and defining empty strings as a valid palindrome.

Solution: To start off, we have to remove all non-alphanumeric characters. To do this we can use the replace function and then convert all characters to lowercase with the toLowercase() function. Then we must iterate through the string and return false if a character found in the string does not match the other side because it is not a palindrome. To accomplish this, we will use a for loop that will iterate through half of the string's length because we will be comparing the front and back halves of the string. The final step to solve the problem will be to return true since if the string is a valid palindrome the for loop would have returned false before the function reached the final line of code. Putting all of this together we get the following solution.

var isPalindrome = function(s){

//removing non alphanumeric characters and converting string to lowercase

  s = s.replace(/\W/g, '').toLowerCase()

  for (let i = 0; i < s.length/2; i++){

//comparing the characters from each end

   if (s[i] !== s[s.length-i-1]) {

	            return false;

	        }
     }
      return true;
   };        

This Solution passes all test cases with a runtime of 76ms