Check if two given strings are isomorphic to each other

The problem, simply

You get two strings, s1 and s2. Say if they are isomorphic, which means they have the same shape.

Same shape means you can swap every letter of s1 for a partner letter and get s2. Two rules: a letter always swaps to the same partner, and two different letters can never have the same partner. A letter may be its own partner.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two strings have the same shape when every pair of spots agrees. If spots i and j hold the same letter in s1, they must hold the same letter in s2, and if they differ in s1, they must differ in s2.

1. If the lengths differ, return false.
2. For every pair of spots i < j, compare "same in s1?" with "same in s2?".
3. If any pair disagrees, return false.

class Solution {
    public boolean isIsomorphic(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                boolean same1 = s1.charAt(i) == s1.charAt(j);
                boolean same2 = s2.charAt(i) == s2.charAt(j);
                if (same1 != same2) return false;   // shapes differ here
            }
        }
        return true;
    }
}

How long it takes: every pair of spots, O(n^2). Extra room: O(1).

Way 2: the clever way

Keep the door keeper's two notebooks. In code they are two hash maps, or two arrays of size 256 for plain letters.

1. If the lengths differ, return false.
2. Walk both strings together. At spot i, look at x = s1[i] and y = s2[i].
3. If the first notebook has x and says something other than y, return false.
4. If the second notebook has y and says something other than x, return false.
5. Otherwise write x to y and y to x, and move on.

The second notebook is the one people forget. Here it saves us:

import java.util.*;

class Solution {
    public boolean isIsomorphic(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        Map<Character, Character> fwd = new HashMap<>();   // s1 letter to s2 letter
        Map<Character, Character> back = new HashMap<>();  // s2 letter to s1 letter
        for (int i = 0; i < s1.length(); i++) {
            char x = s1.charAt(i), y = s2.charAt(i);
            if (fwd.containsKey(x) && fwd.get(x) != y) return false;
            if (back.containsKey(y) && back.get(y) != x) return false;
            fwd.put(x, y);
            back.put(y, x);
        }
        return true;
    }
}

How long it takes: one walk, O(n). Extra room: one entry per different letter, O(k), where k is the size of the alphabet. For plain text that is at most 256, so many people call it O(1).

Watch out for

• Different lengths: return false before the loop, or charAt will crash.
• Boxed letters. fwd.get(x) != y is safe because y is a plain char, so Java compares values. But fwd.get(x) != back.get(y) compares two Character objects and can fail for letters outside Java's small cache. Use .equals when both sides are boxed.
• Isomorphic is about shape, not about letters. ab and ba are isomorphic, and so are ab and cd.

What interviewers ask next

• Can you do it with arrays instead of maps? Yes. Keep last1[c] and last2[c], the last spot each letter was seen. At each spot the two must be equal, then set both to i. It is the same idea in a tighter form.
• Group a list of words by shape? Turn each word into its shape code: replace each letter by the order in which it first showed up. paper becomes 0 1 0 2 3 and title also becomes 0 1 0 2 3. Words with the same code go in the same group.
• Word pattern: does abba match dog cat cat dog? The same two notebooks, but s2 is split into words.
• Find all words in a dictionary that match a pattern? Compare each word's shape code with the pattern's shape code.

Remember this

Grown-up words: the notebooks are hash maps, the partner rule is a one-to-one mapping (a bijection), same shape is isomorphism, and the shape code is a canonical form.