A common interview question to ask junior engineers (or so I’ve heard) is some variation of, given a word or sentence, determine whether or not said word or sentence is a valid palindrome. There are many different ways to go about solving this, but today I’ll cover two different approaches to the most basic, single word version, of this problem.
So first things first, what is a palindrome? According to Dictionary.com it’s “a word, phrase, or sequence that reads the same backward as forward”. “refer” and “racecar” are both examples of palindromic words. Read them right to left and you have the same words as if you were to read them left to right. Before jumping into solving any problem during a technical interview, you should always get clarification on anything that might be vague or unclear. For example, are we considering an empty string a valid palindrome? What if the string contains capital letters? Should we treat those as equal to their lowercase counterparts, and if so, how will we handle these cases and work that into our solution? For the sake of the solutions we’ll walk through here, we’ll assume that we’re given a lowercase string without any extra spaces at the beginning or end, and that an empty string is in fact a valid palindrome.
.split() method. This method divides a string into an ordered list of substrings, and takes optional
limit arguments. This
separator argument is what the string will be split on, and the only one we’ll need to pass in here. According to the Mozilla documents, “When found, separator is removed from the string, and the substrings are returned in an array”. Because we’re dealing with a single string, we can pass “” as the separator argument. This will return an array with each element a character of our string, which we can now call
.reverse() on. This will give us an array of our string characters reversed, which we can call the
.join() method on. This will rejoin our array of reversed characters into a string.
.join() also takes an optional separator argument, which according to Mozilla, “Specifies a string to separate each pair of adjacent elements of the array.” Since we want a single string with no spaces or additional characters, we will pass “” as the
separator argument. This method will return true for an empty string (our edge case), so we don’t need to worry about handling this separately, and can simply return whether or not the reversed string is the same as the original. The code is as follows:
Two Pointers Technique
start variable to
0, and the
end variable to
str.length — 1. Since the length of an empty string is 0,
str.length — 1 of an empty string will be -1. We’ll never actually enter the while loop and will go directly to the return true statement, giving us the following solution:
In terms of which of these solutions is “better”, let’s have a look. The first method,
.split().reverse().join() creates an additional array (from the
.split() method) and creates a new string (from the
.join() method), both of which add to the memory usage of this solution. Because these structures have to be large enough to accommodate all characters of the input string, as the length of the string we input grows, the more space these structures will require in memory to store this additional data. In terms of time, I will not pretend to fully understand how these built in methods work under the hood, but I would imagine each would require going through either the string, or array of characters, once, again changing linearly as the input size grows.
The second solution doesn’t require the creation of any new data structures that are dependent on our input, and thus requires less space in memory. Our worst case scenario in terms of time complexity is that we do in fact have a palindrome, and have to go through every character in our string to come to this conclusion (while technically we’re only ever looping half the number of times as there are letters in the string, the number of times we need to loop will still increase proportionately to the size of our input). This means that as our input size increases, so will the time it takes to run our algorithm, making this linear time complexity as well. So which is “better” to use in a real life program? It really just depends. Sure, the first solution has a worse space complexity, but it’s far more concise and perhaps easier for someone unfamiliar with your code base to read and understand. If you know that you have limited space on the machine you’re running your program, maybe the second option is the better choice.