In this chapter, we will build a program that, given a string, will return true or false depending on whether the given string is a palindrome. A palindrome is:
a word, verse, or sentence (such as "Able was I ere I saw Elba") or a number (such as 1881) that reads the same backward or forward
Given this definition, we already have a good basis for solving this problem. I will use TypeScript for this project, but the solution will look similar in many languages.
Let's stub out some code and get some tests going.
palindrome.ts
export function isPalidrome(input: string): boolean {
return false
}palindrome.test.ts
import { isPalidrome1 } from './palindrome'
describe('#isPalindrome', () => {
test.each([
['123331', false],
['hello', false],
['Able was I ere I saw Elba', true],
['1811', false],
['1881', true],
['madam', true],
['Madam', true],
])('should return "%s" as %p', (input, expected) => {
expect(isPalidrome2(input)).toEqual(expected)
})
})If everything is set up right, we should see something like this when we run npx jest palindrome.test.js. As expected, several of the tests failed.
FAIL palindromes/palindrome.test.ts
#isPalindrome
✓ should return "123331" as false (2 ms)
✓ should return "hello" as false
✕ should return "Able was I ere I saw Elba" as true (1 ms)
✓ should return "1811" as false
✕ should return "1881" as true
✕ should return "madam" as true
✕ should return "Madam" as trueNow that we've got a suitable environment and test suite set up, let's discuss how we might solve this. You can take various approaches to solve this problem, and you might already have some ideas, but for now, let's take a simpler approach.
Approach 1
The definition for a palindrome states that it reads the same forwards as backwards. If you were told to do that by hand, you might write out the given string, then write it out again but backwards below it, and then compare the two strings. It might look something like this:
123331
133321Ok, that's a suitable concept. Let's see if we can make a function that works like that. First, we need to take our input and reverse it; sadly, Typescript doesn't provide a built-in string reverse method, so we're going to have to build our own.
export function isPalidrome(input: string): boolean {
const reversed = input.split('').reverse().join('')
return false
}Here we're using split to turn the string into an array of characters, reversing it and then joining it back into a string. From here, all we need to do is verify that the two strings are the same.
export function isPalidrome(input: string): boolean {
const reversed = input.split('').reverse().join('')
return input === reversed
} FAIL palindromes/palindrome.test.ts
#isPalindrome
✓ should return "123331" as false (2 ms)
✓ should return "hello" as false
✕ should return "Able was I ere I saw Elba" as true (2 ms)
✓ should return "1811" as false
✓ should return "1881" as true
✓ should return "madam" as true
✕ should return "Madam" as trueOk, so that didn't quite work, it's an improvement, but we've still got some failing tests. You might've already spotted this gotcha when we started, but for our isPalindrome to work, it must also be case insensitive.
export function isPalidrome(input: string): boolean {
const reversed = input.split('').reverse().join('')
return input.toLowerCase() === reversed.toLowerCase()
} PASS palindromes/palindrome.test.ts
#isPalindrome
✓ should return "123331" as false (2 ms)
✓ should return "hello" as false (1 ms)
✓ should return "Able was I ere I saw Elba" as true
✓ should return "1811" as false
✓ should return "1881" as true
✓ should return "madam" as true
✓ should return "Madam" as trueGreat, we now have some working code, but there are several issues with this approach which you might've already spotted.
Firstly this implementation is computationally expensive; it requires a lot of data manipulation (string to array to string and then a deep check). Secondly, as a result of the way Typescript (and many other languages) works, this data manipulation significantly increases our memory requirements in the order of 6 times our original string. While the compiler/runtime will clean this up, and you might ask what's the concern for such a simple project, it's something you should be aware of.
Approach 2
Let's try another approach; this will involve reframing the problem. A helpful technique is to consider the inverse of the problem. For example: how can we determine if a string is not a palindrome?
This question is subtly different from before; We're not asking to prove that a string is a palindrome, just if there is a condition that immediately marks a string as not a palindrome. For example, if I give you the string 123331, what can you do to quickly determine that it's not a palindrome?
For 123331 to be considered a palindrome, is must read the same forwards as backwards. With our previous technique, we took the original string, reversed it and compared it letter for letter, something a bit like this:
123331
133321When we compare the string letter by letter, we do it in pairs (vertically). We compare the pairs 1,1, 2, 3, 3, 3, 3, 3, 3, 2, and 1, 1. What do you notice about these pairings?
One thing to notice is that each pair is the first and last letter of the string working inwards. If you take our string and do this operation, you get the pair 1, 1 and the remainder 2333; repeating this gives us 2, 3 remainder 33 and then 3, 3 remainder ``.
When we compare these pairs, we can very quickly evaluate if a string is not a palindrome as soon as we find any pair that does not match. Ahah, that is what we've been looking for. When we compare a pair, we don't necessarily know that the string is a palindrome, but we can say with certainty if it is not a palindrome.
Let's work through our example again but a bit more thoroughly to emphasise the importance of this discovery.
We're given the string 123331. We remove the first and last letters 1, 1, leaving us with 2333. At this point, we can't say that the string is or isn't a palindrome, so we move on.
We now have the string 2333. We pair off the first and last letters into 2, 3, remainder 33. As soon as we compare this pair, we know, with certainty, that this string is not a palindrome. We don't care about the remainder of the string as we've met our failure condition.
If we formalise this discovery, we've gone from "A string is a palindrome when all pairings of letters are the same", to "A string is not a palindrome when any of the pairings of letters are different".
Note: If you're thinking, "Cool Zoe, but what's the point," I'm inclined to agree. In this example, there is very little difference between the two approaches, and this re-defining of the problem yields little benefit. But for more complex examples where the full comparison is an expensive operation, determining a factor that can quickly discard some part of the dataset and/or reduce the problem space is immensely useful. It is a skill worth honing if you ever intend to work on anything with a non-trivial amount of data.
With this new knowledge in hand, let's try a new approach. We will use recursion. We want a function that, given a string, will take the first and last letters, compare them and return false if the first and last letters are different or repeat the operation if the letters are the same.
export function isPalidrome(input: string): boolean {
const first = input[0]
const last = input[input.length - 1]
if (first.toLowerCase() !== last.toLowerCase()) {
return false
}
return isPalidrome3(input.slice(1, input.length - 1))
}This is likely similar to your first go at this (this was mine); if you run this, you'll run into not only failed test cases but this error too.
TypeError: Cannot read property 'toLowerCase' of undefined
What's going on here? If we call isPalindrome('ab'), it will remove the outer letters and call it again with isPalindrome(''). ''[0] will return undefined (in some languages, this might throw an error). So we need to protect this case.
export function isPalidrome(input: string): boolean {
if (input.length === 0) {
return true
}
const first = input[0]
const last = input[input.length - 1]
if (first.toLowerCase() !== last.toLowerCase()) {
return false
}
return isPalidrome3(input.slice(1, input.length - 1))
} PASS palindromes/palindrome.test.ts
#isPalindrome
✓ should return "123331" as false
✓ should return "hello" as false (1 ms)
✓ should return "Able was I ere I saw Elba" as true
✓ should return "1811" as false (1 ms)
✓ should return "1881" as true
✓ should return "madam" as true
✓ should return "Madam" as truePerfect, this now works and is conceptually very close to the method we described. It also has lower memory overhead (Note: this is debatable depending on garbage collection and stack implementation) and is reasonably clear/self-documenting.
Approach 3
Can we do better? The short answer is yes, and you might've already spotted it. Rather than using recursion, we can imitate the pairing off of outer letters by indexing them letter by letter and working inwards in a loop. Something like this:
export function isPalidrome(input: string): boolean {
const lowered = input.toLowerCase()
for (let i = 0; i < lowered.length / 2; i++) {
if (lowered[i] !== lowered[lowered.length - 1 - i]) {
return false
}
}
return true
}This is not only much faster (no stack allocation) but also has a very low memory overhead. Though this is all at the cost of being (arguably) harder to read. This is the final approach I'll show you in this chapter, as anything else is delving into micro-optimisations which is not the focus of this book.
For those interested, there is one somewhat simple improvement you could make, but this is both language and use-case-specific. If you give this function a large string, you're immediately calling .toLowerCase() on it, doubling your memory requirement until the garbage collector releases the reference to input. Instead, you could iterate through the loop and only call .toLowerCase() on each pair of letters as you compare them. Yes, this might introduce a higher CPU cost, but that is the trade-off you are making for lower memory. For a large enough input, this trade-off might be worthwhile.