isPalindrome is an extremely common algorithm that is asked in a lot of job interviews. It's easy enough that a novice programmer should be able to do, but can be expanded upon in several ways that can cause novice programmers to mess up.
The main purpose of the algorithm is to determine if a give string is a palindrome or not.
Pal · in · drome
A word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.
Usually you are asked to write a function, from scratch, to determine if the given string fits the definition of a palindrome.
A common idea someone might have while thinking about this question briefly is that since the string must read the same way forwards as it does backwards, and since strings are usually implemented as collections, then a good first approach would be to reverse the string and compare it to the given string.
Example:
bool is_palindrome(const std::string &str) {
// Create a copy of sent string but in reverse
std::string reversed(str.rbegin(), str.rend());
// If strings are equal then we are a palindrome
return reversed == str;
}However, there are a few issues with the algorithm above. While it does definitely do what we are asked, it can definitely be optimized.
Let's first think about the runtime and space complexity of the algorithm above. Since we are comparing the reversed string to the actual string, we must have a copy of the string, but in reverse. This means that if we let n equal the number of characters in the string, then our space complexity would be linear, or O(n) with respect to the number of characters.
We now know that this has a linear space complexity, what about time? Well to construct the reversed string we must perform a copy, string operations, at least in C++ are expensive and this copy would require linear time, or O(n) to create the reversed string since it copies character by character. Next we return whether or not reversed == str, this is another linear time operation, or O(n), which leaves us with n + n, which is still O(n), since we drop constants. However, remember, in practice these constants do matter, and we can optimize this algorithm further.
We really don't want to make a copy of the string, since again, this is O(n) space. Thus, the only other way we can go about doing this is somehow determining whether or not the string is a palindrome in place. Let's think about how we can do this with the information we have. If we think about what a palindrome is a little more, then we can see that it must be the same both forwards and backwards. Thus this must mean that at every instance the character must equal to last character in a given substring.
If we think about strings as containers of characters then we can draw something like this out, given a palindrome string "racecar".
[ 'r', 'a', 'c', 'e', 'c', 'a', 'r' ]Now if we start by just trying to do the above, that is check if the first character of a given substring is equal to the last character of that given substring. In the first iteration our "substring" is the string itself, thus we can check the begin and end chars.
[ 'r', 'a', 'c', 'e', 'c', 'a', 'r' ]
^ ^Thus we can see that this is in fact the case, now we can try on a smaller substring, that is the substring with the begin and end of the previous substring not being considered.
[ 'r', 'a', 'c', 'e', 'c', 'a', 'r' ]
^ ^And again we see that this is also the case, you can continue the process until you get to:
[ 'r', 'a', 'c', 'e', 'c', 'a', 'r' ]
^
^Here both the begin "pointer" and the end "pointer" equal each other, this happens when we have an odd sized string. This is fine however, as a single character is always a palindrome and our assumption still holds since a begin and end of the substring "e" are both equal.
Thus we have devised a much better algorithm, let's code it up!
bool is_palindrome(const std::string &str) {
// Since using unsigned we don't want to do bad things when
// doing str.size() - 1, so if size == 0, we can either
// consider the empty string a palindrome or not, you decide!
if (str.size() == 0) return true;
unsigned b = 0;
unsigned e = str.size() - 1;
while (b < e) {
if (str[b] != str[e]) return false;
++b; --e;
}
return true;
}The above does the process described in our algorithm, using indices to the string instead of "pointers". However, this can be quickly rewritten to use C++ iterators, pointers, or whatever you would like to use for traversal.
Measuring the complexity of the above algorithm we see that we have gone from linear space to constant space, or O(1), which is much better. The time complexity, in terms of Big-Oh has not technically improved as we must still traverse the entire string in the worst case, however, we do have a lower constant factor since we only perform at most one full traversal through the string.
This is a great problem to know as it gets asked frequently, and is a good problem for seeing how the most obvious and maybe (most readable?) solutions aren't always the best in terms of performance.
Want to run a live demo of this algorithm? Go here