Growing with the Web

Determine if a string is a palindrome

Published , updated
Tags:

This article looks at the interview question - Determine if a string is a palindrome (text that is spelled the same when reversed).

Analysis

This problem can be trivially solved by looping through each character and checking it against the character on the opposite side. There is a problem with this though because half the work being done is redundant as it’s checking all characters two times. Consider the palindrome "madam", this algorithm would make the following comparisons:

m ↔ m
a ↔ a
d ↔ d
a ↔ a
m ↔ m

All that needs to be compared to prove it’s a palindrome are the first two characters against the last two since the middle one does not need to be checked:

m ↔ m
a ↔ a

This leads us to our initial solution:

function isPalindrome (text)
  if text is null
    return false
  left ← 0
  right ← text.length - 1
  while (left < right)
    if text[left] is not text[right]
      return false
    left ← left + 1
    right ← right - 1
  return true

If an interviewer ever asks this question, the above solution alone will likely not impress them too much. There are several ambiguities in the question that should be clarified before getting into the code. Failing to clarify the question could make you come off as someone who rushes the job without thinking too hard about what the right solution is. So the questions:

  • Is the solution meant to be case sensitive?
  • Do phrase palindromes need to be taken into account?
  • What about punctuation?

The easiest and most elegant way to augment our code to take these new pieces of information into account is to use a regular expression. We can craft a regex that removes the spaces and punctuation. Then all that needs to be done is to transform the text into lowercase and pass the new string into the original solution.

function isPhrasePalindrome (text)
  remove regex "\[^a-zA-Z\]" from text
  text ← lowercase(text)
  return isPalindrome(text)

For those unfamiliar with regex, [^a-zA-Z] means to match characters ([...]) that are not (^) in the range a-z and A-Z (a-zA-Z).

Complexity

An interviewer may ask about the time complexity for this algorithm to try and trick the candidate. The first function isPalindrome has a time complexity of O(n / 2) which is equal to O(n) since Big-O notation ignores constant terms.

isPhrasePalindrome is also O(n) since string transformations are applied to each of the text’s characters.

Code

public static boolean isTextPalindrome(String text) {
    if (text == null) {
        return false;
    }
    int left = 0;
    int right = text.length() - 1;
    while (left < right) {
        if (text.charAt(left++) != text.charAt(right--)) {
            return false;
        }
    }
    return true;
}

public static boolean isPhrasePalindrome(String text) {
    String chars = text.replaceAll("[^a-zA-Z]", "").toLowerCase();
    return isTextPalindrome(chars);
}
function isTextPalindrome(text) {
  if (text === undefined) {
    return false;
  }
  var left = 0;
  var right = text.length - 1;
  while (left < right) {
    if (text[left++] !== text[right--]) {
      return false;
    }
  }
  return true;
}

function isPhrasePalindrome(text) {
  var chars = text.replace(/[^a-zA-Z]/g, '').toLowerCase();
  return isTextPalindrome(chars);
}

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

Like this article?
Subscribe for more!