Write a function to determine whether or not a string is a palindrome.

 

A palindrome is a string that can be read from right to left, and yet still remains the same as the string read left to right. For example, ‘racecar’ and ‘level’ are both palindromes because if you read the strings from right to left they are equivalent to the strings read left to right.

So, how shoud we approach writing a function that, given a string as input, determines whether or not that string is a palindrome? What is the defining feature of a palindrome? That, when read from right to left it is the same as the string read left to right.

What if we just create a temporary string where we store the string read from right to left, and then compare that to the original string. If they are the same, then it’s a palindrome, if different then the string is NOT a palindrome. Sounds simple enough, here’s what the pseudocode would look like:

function bool isPalindrome(String input)
{
	int len = input.length();
	
	String temp;
	
	for(j = 0; j<len; j++)
	{		
		// read from input backwards
		// and populate temp
		temp[j] = input[len - 1];		
	
		len = len - 1;				
	}
	
	/* now, compare temp to input
	   if they are the same then
	   we know that input is a palindrome
	   if not, then it's not
	*/
	
	if(temp.equals(input))
		return true;
	
	else return false;
}

Could we find a better way of solving this? That’s a very broad question. When asked a broad question in an interview situation, it helps to ask yourself another, more specific and incisive question. The better question to ask is what is inefficient about our solution? Well, we do use a temp variable.

Now, is it possible to come up with a solution that doesn’t use a temp variable, so that we only use the input string? Well, what do we know about palindromes? Let’s take ‘racecar’ as an example. We can see that the first letter must be the same as the last, the second letter must be the same as the second to last, and so forth. So, we can also say that if the first letter is not the same as the last, and the second letter is not the same as the second to last then we do NOT have a palindrome. This sounds like we can translate this into a more efficient algoritm, without having to use the temp string variable. Here’s what it would look like:

function bool isPalindrome(String input)
{
	int len = input.length();
	
	bool isPalindrome = true;
	
	
// only have to iterate through half the length of the string
	for(j = 0; j<len/2; j++)
	{
		if(input[j] != input[len - 1 -i])
		{
			isPalindrome = false;	
			break;
			
		}
	}
	
	return isPalindrome;
}

Note how we were able to improve our solution to the problem simply by asking ourselves if it could be improved. This is typically all that’s needed – just ask yourself if it can be improved and often you will realize that it can be. Also notice that the function that we’ve written is very simple and will not ignore punctuation, whitespace, and case. For instance, "A man, a plan, a canal, Panama!", is considered to be a palindrome. But, the function that we wrote will not consider it to be a palindrome. This is OK, but it is definitely worth pointing out in an interview, because interviewers are always looking out for developers who are detail oriented. This trait is simply invaluable in the increasingly complex software industry.


Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.



FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon