Isomorphic Strings

Share

Given two strings s and t, decide whether they are isomorphic: whether the characters of s can be replaced to get t, where every copy of a character is replaced by the same character, and no two different characters are replaced by the same one. A character may map to itself. This is LeetCode 205.

Example 1
Input: s = "egg", t = "add"
Output: true
Explanation: e → a, g → d.
Example 2
Input: s = "foo", t = "bar"
Output: false
Explanation: o would have to become both a and r.
Example 3
Input: s = "paper", t = "title"
Output: true

How to Think About It

Step 1: The mapping must work in both directions

Two things can break it:

  • one character of s paired with two different characters of t ("foo" and "bar": o pairs with a and r);
  • two characters of s paired with the same character of t ("ab" and "cc": a and b both pair with c).

A single map from s to t only catches the first. Two maps, one per direction, catch both.

Step 2: A neater check with last positions

Two strings are isomorphic exactly when, at every index i, s[i] and t[i] were last seen at the same position (or both never seen). Matching "history" in both strings means the characters are always paired the same way.

Store lastS[c] and lastT[c], the last index (plus one, so that 0 means "not seen") of each character. At each i, compare lastS[s[i]] with lastT[t[i]], then update both to i + 1.

Walkthrough

s = "badc", t = "baba". A one-way map from s to t would wrongly accept this pair.

is[i], t[i]lastS[s[i]]lastT[t[i]]Same?
0b, b0 (never)0 (never)yes
1a, a00yes
2d, b0 (d is new)1 (b at index 0)no: return false

d and b would both have to map to b, which is not allowed.

Java Solution

Arrays of 256 entries cover every ASCII character, as the problem allows.

Java
import java.util.Arrays;

public class IsomorphicStrings {

    public static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        // last position (+1) where each character was seen; 0 means "not seen yet"
        int[] lastS = new int[256];
        int[] lastT = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            char b = t.charAt(i);
            if (lastS[a] != lastT[b]) {
                return false;                 // a and b were last paired differently
            }
            lastS[a] = i + 1;
            lastT[b] = i + 1;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("egg", "add"));       // true
        System.out.println(isIsomorphic("foo", "bar"));       // false
        System.out.println(isIsomorphic("paper", "title"));   // true
        System.out.println(isIsomorphic("badc", "baba"));     // false
    }
}

The original implementation, IsomorphicStrings.java, is on GitHub.

Complexity
  • Time: O(n).
  • Space: O(1): two fixed arrays.

The same two-way check, applied to letters and words, is Word Pattern.