Palindrome pairs with a reversed-word trie

Why this matters

A palindrome is a word or phrase that reads the same forwards and backwards. "level" is one. "abba" is another. "abc" is not, because backwards it reads "cba".

Take two words and join them end to end. "abcd" joined with "dcba" gives "abcddcba", which is a palindrome. The order matters. "dcba" joined with "abcd" gives "dcbaabcd", which is also a palindrome. A join of two words that reads the same both ways is called a palindrome pair.

The task in this lesson: given a list of words, find every ordered pair of different words whose join is a palindrome. This is a well-known interview question. The simple solution joins every pair and tests each join letter by letter. That is correct, but the number of joins grows quickly with the list length. This lesson builds a faster solution. It uses a trie, a tree of letters that lesson 01 of this module introduced. Lesson 02 showed how a trie finds words that start with a prefix. This lesson uses the same walk to match a word against a reversed word.

Terms used in this lesson

A word list is the input, a list of strings. Each word has an index, which is its position in the list. Counting starts at 0, so the first word has index 0.

A pair written [i, j] means the word at index i comes first and the word at index j comes second. With the words "abcd" at index 0 and "dcba" at index 1, the pair [0, 1] stands for "abcd" + "dcba". The pair [1, 0] is a different pair with a different join.

A reversed word is the same letters in the opposite order. The reverse of "abc" is "cba". In Python you can get it with the slice s[::-1], which walks the string from its last letter to its first.

A trie is a tree of letters. The top is the root, an empty starting point. Each step down the tree adds one letter. A path from the root to a node (one box in the tree) spells a prefix. In this lesson each node also stores the index of a word that ends at that node. If no word ends there, the stored index is -1.

A prefix is the first few letters of a word. "ca" is a prefix of "cat". A suffix is the last few letters. "at" is a suffix of "cat".

A brute force solution tries every possibility. It is slow but easy to trust, so this lesson also uses one as a checker.

The slow way first

Start with three words: "bat" at index 0, "tab" at index 1 and "cat" at index 2. There are six ordered pairs of different words. Each one is a join to test.

Check "battab" by reading it backwards: b, a, t, t, a, b. It is the same. Check "batcat" backwards: t, a, c, t, a, b. It is different from b, a, t, c, a, t, so it is not a palindrome.

With n words there are n times (n - 1) ordered pairs. A list of 1,000 words has 999,000 joins, and each join is checked one letter at a time. Most of that work is wasted, because most joins are not palindromes. The trie solution looks only at the words that could work.

The key idea: split each pair by length

Take an ordered pair. Call the first word a and the second word b. There are two cases.

Case 1: b is not longer than a. The join a + b is a palindrome exactly when two things are true:

• b equals the reverse of the first len(b) letters of a, and
• the letters of a after those first letters form a palindrome.

Example: a = "lls" and b = "ll". The first two letters of a are "ll". The reverse of "ll" is "ll", which equals b. The letters left over in a are "s", and "s" is a palindrome. The join "lls" + "ll" is "llsll", which reads the same both ways.

Case 2: b is longer than a. The join is a palindrome exactly when two things are true:

• a equals the reverse of the last len(a) letters of b, and
• the letters of b before those last letters form a palindrome.

Example: a = "s" and b = "lls". The last letter of b is "s", and its reverse is "s", which equals a. The letters before it are "ll", a palindrome. The join "s" + "lls" is "slls", which reads the same both ways.

Why does this hold? A word that reads the same both ways has to mirror itself. When the first word is at least as long, its opening letters must mirror the second word. When the second word is longer, its closing letters must mirror the first word. The rest must also be a palindrome, or the middle would not match.

Each case becomes one walk through a trie. Case 1 needs a trie that stores reversed words. Case 2 needs a trie that stores words as they are written. The program makes two passes, one for each case.

Pass 1: a trie of reversed words

For case 1 we need every word b whose reverse is a prefix of a. If the trie holds the reversed words, then a's letters can be matched against the trie in one walk from the root. Each letter of a moves one step down.

Use this list, which has four palindrome pairs:

index 0: abcd
index 1: dcba
index 2: lls
index 3: s
index 4: sssll

Reverse each word and insert it with its original index:

• "abcd" reversed is "dcba", stored with index 0.
• "dcba" reversed is "abcd", stored with index 1.
• "lls" reversed is "sll", stored with index 2.
• "s" reversed is "s", stored with index 3.
• "sssll" reversed is "llsss", stored with index 4.

The trie looks like this. A number in square brackets is the index stored at that node.

root
 +-- a -- b -- c -- d [1]
 +-- d -- c -- b -- a [0]
 +-- l -- l -- s -- s -- s [4]
 +-- s [3]
      +-- l -- l [2]

Now walk the first word, "abcd" at index 0. Look at the node after each letter:

• After "a": no word ends here. Keep going.
• After "ab": no word ends here. Keep going.
• After "abc": no word ends here. Keep going.
• After "abcd": index 1 is stored here. Word 1 is "dcba", and its reverse "abcd" is the prefix we just matched. Check the letters of "abcd" left after the match. There are none, and an empty part counts as a palindrome. Add the pair [0, 1].

Next walk the word "sssll" at index 4. After its first letter "s", the node has index 3, which is the word "s". Its reverse "s" matches the start of "sssll". The letters of "sssll" left over are "ssll". Those are not a palindrome: the first letter is s, the last letter is l. So no pair is added. Joining "sssll" + "s" gives "ssslls", and that is not a palindrome either. The palindrome check is required, because a prefix match alone is not enough.

One more rule: a walk can reach the node of the same word. The word "s" at index 3 matches itself when we walk "s". The code skips a match where the two indexes are the same, because a word cannot pair with itself.

Pass 2: a trie of words as written

Case 2 needs a shorter word a that equals the reverse of the last letters of b. Walk b from its last letter toward its first letter. The letters you read in that order spell the reverse of b's ending, and that reverse is exactly a. So this time the trie stores the words as they are written, and each walk starts at the end of b.

Use the same list. Begin with the word "lls" at index 2, read from the end. The letters read are "s", then "l", then "l".

• After "s": the forward trie has a node "s" with index 3, which is the word "s". Its letters match the end of "lls". The letters before them are "ll", a palindrome. Add the pair [3, 2], which joins "s" + "lls" = "slls".
• After "sl": the forward trie has no such path, so stop.

Now the word "sssll" at index 4, read from its end. The letters read are "l", "l", "s", "s".

• After "l": the node exists, but no word ends here.
• After "ll": the node exists, but no word ends here.
• After "lls": index 2 is stored here, the word "lls". The letters of "sssll" before the last three are "ss", a palindrome. Add the pair [2, 4], which joins "lls" + "sssll" = "llssssll".
• After "llss": there is no such path, so stop.

The walk must stop before it reads the whole word. Reading all the letters would match a word of the same length as b, and pass 1 already covers those. The walk reads at most len(b) minus 1 letters.

The two passes never produce the same pair. Pass 1 only adds pairs where the first word is at least as long as the second. Pass 2 only adds pairs where the first word is shorter. The two groups do not overlap.

The full program

The program below does both passes. It also has a small main part that runs four word lists.

The program prints:

abcd,dcba,lls,s,sssll -> [[0, 1], [1, 0], [3, 2], [2, 4]]
bat,tab,cat -> [[0, 1], [1, 0]]
a,aa -> [[1, 0], [0, 1]]
aba -> []

The first line matches the pairs found by hand. [0, 1] and [1, 0] come from pass 1, and [3, 2] and [2, 4] come from pass 2. The pairs appear in the order the passes find them, so the order changes if you change the loops.

The word list a,aa shows that both orders can be valid. "a" + "aa" is "aaa", and "aa" + "a" is also "aaa". Both pairs are kept because the task asks for ordered pairs.

The palindrome check uses a slice. s[start:end] copies the letters from start up to, but not including, end. Comparing the copy with its own reverse, part[::-1], is the shortest correct check. It copies the letters twice, so a faster check that compares from both ends would save work on long words. The lesson keeps the slice version because it is easy to read.

The dictionary children keeps each letter as a one-letter string. node.children.get(ch) returns None when no child exists for ch, which the code checks before it reads anything from the node.

Checking against a slow version

A slow version that tests every join is easy to trust. The check below is a brute force that joins every ordered pair and tests the join. It runs the fast method and the slow one on 20,000 random word lists, and it compares the two results. The lists use only the letters a and b, which makes palindromes common. Each list has between 1 and 7 different words of length 1 to 4. The results are compared as sorted lists, because the two methods find the same pairs in different orders.

import random
 
 
def brute(words):
    out = []
    for i in range(len(words)):
        for j in range(len(words)):
            if i == j:
                continue
            joined = words[i] + words[j]
            if joined == joined[::-1]:
                out.append([i, j])
    return out
 
 
rng = random.Random(1)
bad = 0
for _ in range(20000):
    count = rng.randint(1, 7)
    words = set()
    while len(words) < count:
        length = rng.randint(1, 4)
        words.add("".join(rng.choice("ab") for _ in range(length)))
    words = list(words)
    if sorted(find_palindrome_pairs(words)) != sorted(brute(words)):
        bad += 1
print("mismatches in 20000 random cases:", bad)

The result of my run, with find_palindrome_pairs from the program above in the same file, was:

mismatches in 20000 random cases: 0

How much work it does

Let n be the number of words and L the length of the longest word. Each word is walked at most L steps in each pass. At each step the program may run a palindrome check, which takes up to L letter comparisons, or a slice of up to L letters. So the total work is about n times L times L.

The brute force version tests every ordered pair, and each test joins two words and checks up to 2L letters. That is about n times n times L. When there are many words and the words are short, the trie version is much faster. When the words are very long, the palindrome checks add up, and a faster palindrome check would help. That improvement is outside this lesson.

Memory works the same way. Each word adds at most L nodes to each of the two tries. Shared beginnings, such as the many words that start with "a", share nodes.

Common mistakes

Pairing a word with itself

Without the check j != i, the program pairs a word with itself when the word is a palindrome. I made a copy of the program without that check and ran it on the list aba. The correct answer is an empty list.

aba -> [[0, 0]]

The word "aba" reversed is "aba", so the walk finds its own index. The pair [0, 0] joins "aba" with itself, which the task does not ask for. Keep the check that the two indexes differ.

Counting equal lengths twice

Pass 2 must stop before it reads the whole word. If the loop runs one step too far, equal-length pairs appear twice. I made a copy of the program with range(1, n + 1) in pass 2 and ran it on ab and ba. The correct answer is [[0, 1], [1, 0]]. The copy printed:

[[0, 1], [1, 0], [1, 0], [0, 1]]

Pass 1 already finds equal-length pairs, so pass 2 must leave them out.

Forgetting the None check

When a letter is not in the trie, children.get returns None. The next line then reads an attribute from None. I made a copy with the check if node is None: break removed, and ran it on the words abc and xyz. The output was:

AttributeError: 'NoneType' object has no attribute 'word_index'

The message names the type, NoneType, and the attribute that could not be read. The fix is the check that stops the walk when there is no child.

Comparing with reversed()

Python has a function called reversed that gives the letters in reverse order, but it returns an iterator, not a string. A comparison between a string and an iterator is always False, and Python does not warn about it. I made a copy with part == reversed(part) in place of part == part[::-1] and ran it on the sample list. The program printed:

abcd,dcba,lls,s,sssll -> []

The sample has four palindrome pairs, so the empty answer is wrong. Use the slice part[::-1], which returns a string that can be compared with part.

Forgetting the palindrome check

Without is_palindrome, pass 1 would accept any prefix match. For the word "sssll" at index 4, the walk matches the word "s" at index 3 and adds [4, 3]. But "sssll" + "s" is "ssslls", which is not a palindrome. Each prefix match needs its leftover letters checked. On the sample list the copy without the check printed [[0, 1], [1, 0], [4, 3], [3, 2], [2, 4]], which has the extra pair [4, 3].

Practice

Exercise 1

Find every palindrome pair in the list lls, ll, s (indexes 0, 1 and 2). Write each pair with its join.

Show the answer: The pairs are [0, 1] and [2, 0]. The join lls + ll is "llsll", which reads the same both ways. The join s + lls is "slls", which reads the same both ways. Running the program on the list gives [[0, 1], [2, 0]], the same answer.

Exercise 2

For the list ab, ba, write the correct answer. Then explain what goes wrong if pass 2 uses range(1, n + 1) instead of range(1, n).

Show the answer: The correct answer is [[0, 1], [1, 0]]. The join ab + ba is "abba" and ba + ab is "baab", and both are palindromes. With range(1, n + 1), pass 2 also reads the whole word. For the word ba, reading all of its letters from the end gives "ab", which is index 0. That adds [0, 1] a second time. The same happens for the word ab, which adds [1, 0] again. Both extra pairs are duplicates of pairs pass 1 already found.

Exercise 3

Why does the list aba have no palindrome pairs, even though "aba" reads the same both ways?

Show the answer: The only ordered pair is the word with itself, [0, 0]. The task asks for two different words, so the pair is not allowed. The check j != i removes it, and the program returns an empty list.

Exercise 4

Write a brute force function brute(words) that tests every ordered pair of different indexes. Use it to check the list abcd, dcba, lls, s, sssll.

Show the answer: The function is the brute in the checking section above. It loops over every i and every j, skips the pairs where i == j, joins the two words, and keeps the pair when the join reads the same both ways. On this list it finds the same four pairs as the fast method: [0, 1], [1, 0], [2, 4] and [3, 2]. The order differs, because the brute force loops over the first index before the second. Brute force tests every join, so it does not need the case split. It is the checker for the faster method, and its result must match once both are sorted.

Summary

• A palindrome pair is an ordered pair of different words whose join reads the same both ways.
• If the first word is at least as long as the second, the second must be the reverse of the first word's opening letters, and the rest of the first word must be a palindrome.
• If the second word is longer, the first must be the reverse of the second word's closing letters, and the rest of the second word must be a palindrome.
• Pass 1 uses a trie of reversed words, and each word is walked from its first letter.
• Pass 2 uses a trie of words as written, and each word is walked from its last letter, stopping before the whole word is read.
• Always check that the two indexes differ, and always check the leftover letters are a palindrome.