Isomorphic strings and word patterns in Python

Why this matters

Some checks ask whether two sequences follow the same template. Imagine a secret code where each letter always stands for one other letter. A message is valid only if the code is used the same way every time. Another example is a list of words that must follow a pattern such as "first word, second word, second word, first word". In both cases you need a mapping: a rule that says which item on one side goes with which item on the other side.

A good mapping is one to one. Each item on the left maps to exactly one item on the right, and two different items on the left never map to the same item on the right. This lesson shows how to check both parts of that rule with two dicts. A dict stores pairs of a key and a value and looks up a value quickly from its key.

The lesson covers two problems that use the same check:

• Isomorphic strings. Two strings have the same length, and each letter in the first string maps to one letter in the second string in a way that is one to one. For example, egg and add are isomorphic, because e maps to a and g maps to d every time they appear.
• Word patterns. A pattern such as abba and a sentence such as dog cat cat dog match when each pattern letter maps to one word and each word maps back to one pattern letter.

Two definitions with examples

Take the strings egg and add. Line them up letter by letter:

• Position 0: e and a. Remember that e goes with a.
• Position 1: g and d. Remember that g goes with d.
• Position 2: g and d. This is the same pair as position 1, so it is consistent.

The strings match, so they are isomorphic. The lengths are also equal, which is required.

Now take foo and bar:

• Position 0: f and b. f goes with b.
• Position 1: o and a. o goes with a.
• Position 2: o and r. But o already goes with a, not r.

The check fails at position 2, so foo and bar are not isomorphic.

For word patterns, take the pattern abba and the sentence dog cat cat dog. The sentence has four words. Split it at each space to get the list dog, cat, cat, dog. Now match each pattern letter with the word in the same position:

• a goes with dog.
• b goes with cat.
• The next b goes with cat, which matches.
• The last a goes with dog, which matches.

The pattern matches. The same test with the sentence dog cat cat fish fails at the last position, because a goes with dog and the last word is fish.

The mistake: one dict is not enough

A first attempt often uses one dict, from each letter in the first string to the letter in the same position in the second string. The dict is checked each time a letter appears again. This catches a letter that maps to two different letters. It does not catch two different letters that map to the same letter.

Take badc and baba. Build the one-dict version:

• Position 0: b and b. Map b to b.
• Position 1: a and a. Map a to a.
• Position 2: d and b. d is new, so map d to b. The dict has no rule that d must be different from b.
• Position 3: c and a. Map c to a.

Every check passed, so the one-dict version says True. But the second string is baba, and the letter b now stands for both b and d from the first string. The mapping is not one to one, so the correct answer is False.

The fix is a second dict that goes the other way. It maps each letter on the right side back to the letter on the left side. With both dicts, the check at position 2 sees that b already maps back to b, not to d, and returns False.

Two dicts: the rule in one sentence

At each position, the left item and the right item must agree with what the two dicts already say:

• If the left item has a stored partner, the partner must be the right item.
• If the right item has a stored partner, the partner must be the left item.
• If either side has no partner yet, store the new pair in both dicts.

This is the whole check. The code below uses one function for all of it, so that the same rule is written once and used for both problems.

In Python the check for a stored partner is in. A value of None would not work as a marker, because None could be a real stored value in some other problem. Testing with in avoids that question.

Worked example 1: egg and add

Here are the steps for egg and add. The dicts are written the way Python prints them, in backticks.

• Position 0, pair e and a. Left dict has no e, so store e to a. Right dict has no a, so store a to e. Left dict is {'e': 'a'}, right dict is {'a': 'e'}.
• Position 1, pair g and d. Neither is stored, so store g to d and d to g. Left dict is {'e': 'a', 'g': 'd'}, right dict is {'a': 'e', 'd': 'g'}.
• Position 2, pair g and d. The left dict has g to d, which matches. The right dict has d to g, which matches. Nothing is stored, and the check continues.

The loop ends with no failure, so the answer is True.

Worked example 2: word pattern with a match

Take the pattern abba and the sentence dog cat cat dog.

• Position 0, pair a and dog. Store a to dog and dog to a.
• Position 1, pair b and cat. Store b to cat and cat to b.
• Position 2, pair b and cat. Both stored partners match.
• Position 3, pair a and dog. Both stored partners match.

The answer is True.

Worked example 3: two letters that share one word

Take the pattern abba and the sentence dog dog dog dog. Every word is the same, so the pattern says that a and b must be different words. The check should fail.

• Position 0, pair a and dog. Store a to dog and dog to a.
• Position 1, pair b and dog. The left side b has no partner, so the left dict accepts b to dog. The right side dog already has partner a, which is not b, so the check returns False.

The right-side dict is the part that catches this. A one-dict version that only goes from pattern letter to word would accept it, because b has no earlier partner. This is the same mistake as the badc and baba case, written with words.

Worked example 4: a long pattern that fails at the end

Take the pattern abcabc and the sentence red green blue red green red. The pattern repeats the first three letters, so the last word should match the third word, blue. Check each position:

• Positions 0 to 2, pairs a with red, b with green and c with blue. Each pair is stored in both dicts.
• Position 3, pair a with red. Both stored partners match.
• Position 4, pair b with green. Both stored partners match.
• Position 5, pair c with red. The left dict says c goes with blue, not red. The check returns False.

Only the last word breaks the pattern, but that is enough. The check has to look at every position before it can say True.

A second way: first positions

There is a second way to check isomorphic strings. For each letter, record the position where it first appears. Two strings are isomorphic exactly when their two lists of first positions are the same.

Take egg. The first e is at position 0. The first g is at position 1, and the second g repeats position 1, so its entry is 1 again. The list is [0, 1, 1]. The string add gives the same list, so the two are isomorphic. For badc, every letter is new, so the list is [0, 1, 2, 3]. For baba, the list is [0, 1, 0, 1], which is different, so badc and baba are not isomorphic.

This method uses one dict, from each letter to its first position, and then compares two lists. The code is short:

[0, 1, 1]
[0, 1, 1]
[0, 1, 2, 3]
[0, 1, 0, 1]
True
False

The two methods agree on the examples above. Agreeing on examples is a test of the idea, not a proof. The two-dict method is the one that carries over to word patterns, because it checks each pair against its partner as it goes.

The code

The program uses one generic function, same_shape, for both problems. is_isomorphic passes the two strings straight in, because a string is a sequence of letters. word_pattern passes the pattern string and the sentence split into words. The one_map_only function is included to show the mistake from earlier, and it is not used by the other two checks.

isomorphic("egg", "add") = True   one-map-only = True
isomorphic("foo", "bar") = False   one-map-only = False
isomorphic("paper", "title") = True   one-map-only = True
isomorphic("ab", "aa") = False   one-map-only = True
isomorphic("badc", "baba") = False   one-map-only = True
isomorphic("", "") = True   one-map-only = True
wordPattern("abba", "dog cat cat dog") = True
wordPattern("abba", "dog cat cat fish") = False
wordPattern("aaaa", "dog cat cat dog") = False
wordPattern("abba", "dog dog dog dog") = False
wordPattern("abc", "b c a") = True
wordPattern("a", "") = True

The lines show the difference between the two methods. On ab and aa, the one-dict version says True, but the right answer is False, because a and b on the left both map to a on the right. The two-dict version says False. On badc and baba, the same thing happens.

The code parts are these.

zip(left, right) walks two sequences side by side. It gives the pairs (a, b) for each position. It stops at the shorter sequence, which is why the length check comes first.

if len(left) != len(right) is the length check. Without it, zip would quietly drop the extra items, and the mistakes section below shows the wrong answer that follows.

if a in left_to_right tests for a stored partner. The check left_to_right[a] != b compares the stored partner with the new one. Python compares strings by their text, so != is the right test for words and letters.

sentence.split(" ") cuts the sentence at each space and returns a list of the pieces. The empty sentence case is covered in the mistakes section.

Common mistakes

Using one dict only

The one_map_only function above shows the error. It passes every pair that has two letters mapping to one letter, such as ab and aa, and badc and baba. The fix is the second dict, as in same_shape.

Leaving out the length check

When the two sequences have different lengths, the loop must not read past the end of the shorter one. Python's zip stops at the shorter sequence, so the length check is easy to forget, and then the wrong answer comes back with no error. This program checks the pattern aab against the two words dog dog:

def no_length_check(left, right):
    left_to_right = {}
    right_to_left = {}
    for a, b in zip(left, right):
        if a in left_to_right and left_to_right[a] != b:
            return False
        left_to_right.setdefault(a, b)
        if b in right_to_left and right_to_left[b] != a:
            return False
        right_to_left.setdefault(b, a)
    return True
 
 
print(no_length_check("aab", ["dog", "dog"]))

True

The answer should be False, because the pattern has three letters and the sentence has two words. zip dropped the third letter, so the check never saw it. The fix is the len check at the top of same_shape.

A version that uses an index instead of zip gives an error rather than a wrong answer. With the same inputs, the loop reads right[2], which does not exist:

def index_no_check(left, right):
    left_to_right = {}
    right_to_left = {}
    for i in range(len(left)):
        a = left[i]
        b = right[i]
        if a in left_to_right and left_to_right[a] != b:
            return False
        left_to_right.setdefault(a, b)
        if b in right_to_left and right_to_left[b] != a:
            return False
        right_to_left.setdefault(b, a)
    return True
 
 
print(index_no_check("aab", ["dog", "dog"]))

Traceback (most recent call last):
  ...
IndexError: list index out of range

The lines between the first and last line show file names and line numbers, which differ on your machine. The last line is the same everywhere.

Comparing words with is

In Python, == asks whether two values are equal, and is asks whether they are the same object in memory. Two words with the same letters can be separate objects. Splitting a sentence creates new string objects, so two equal words may or may not be the same object. Here is a check on the sentence dog cat dog:

first == again: True
first is again: False

The two words are equal, so == is the right test. A check that uses is would call two equal words different and give a wrong answer. The usual case where is is correct is None, as in if value is None.

Splitting an empty sentence

"".split(" ") returns a list with one empty string, not an empty list. That means the pattern a matches an empty sentence, because one pattern letter and one empty word have the same length. The function above returns True for word_pattern("a", ""). If your problem says an empty sentence has no words, check for it before the split. Calling split() with no argument instead returns an empty list for an empty or all-space string, which is a different rule.

[''] []

Practice

Exercise 1

Are ab and ba isomorphic? Show the dict steps.

Show the answer

Yes. Position 0 pairs a with b, so the left dict stores a to b and the right dict stores b to a. Position 1 pairs b with a. Neither is stored yet, so the left dict stores b to a and the right dict stores a to b. Every pair agrees, so the answer is True. The function prints True for this input.

Exercise 2

Does the pattern abab match the sentence cat dog cat dog?

Show the answer

Yes. a goes with cat and b goes with dog. Both repeat in the right places, and no two pattern letters share a word. The answer is True.

Exercise 3

Does the pattern abc match the sentence dog dog cat? Name the position where the check fails.

Show the answer

No. The check fails at position 1. a already goes with dog from position 0. Position 1 pairs b with dog, but the right side dog already goes back to a, not b. The function returns False for this input.

Exercise 4

Explain why the length check comes before the loop, and not inside it.

Show the answer

The loop walks both sequences side by side. If the lengths differ, the loop reaches a position that one sequence does not have, which raises an error when the code uses an index and silently drops items when it uses zip. Checking the lengths once, before the loop, returns False immediately and never reads past the end.

Exercise 5

Write a test that shows the one-dict version is wrong, using words instead of letters. Give the pattern, the sentence and the answer the correct check should return.

Show the answer

Use the pattern abba and the sentence dog dog dog dog. The correct answer is False, because a and b must be different words. A one-dict version that only goes from pattern letter to word would store a to dog, then accept b to dog, and return True. Adding a second dict from word to letter catches this at position 1. The wordPattern example in this lesson returns False for this input.

Summary

• A one-to-one mapping needs two checks: each left item has one partner, and each right item has one partner.
• Use two dicts, one for each direction, and check both at every position.
• A one-dict check passes badc and baba, which is wrong. The second dict is what catches it.
• Check the lengths before the loop, because the two sequences must be the same length.
• Compare strings and words with ==, and use is only for None.
• Splitting an empty sentence with split(" ") gives one empty word, so decide what an empty input should mean before you split.