Check if Two Strings Are Isomorphic

Easy10–15 min

Topics

StringHash Table

Companies

AmazonYelpSnapchat

Given two strings s and t of the same length, return true if they're isomorphic — meaning the characters of s can be replaced, one-for-one and consistently, to get exactly t. No two characters may map to the same character, but a character may map to itself. Comparing every pair of positions directly confirms consistency but costs O(n²). The faster approach walks both strings together while tracking the mapping both ways — s-to-t and t-to-s — in two hash maps. Checking both directions at every step is what catches both kinds of broken mapping in a single pass.

Test Case 1:

Input:s = "egg", t = "add"

Output:true

Explanation:e→a and g→d — a consistent one-to-one mapping in both directions.

Test Case 2:

Input:s = "foo", t = "bar"

Output:false

Explanation:f→b works, but the two o's in "foo" would need to both map to 'a', yet the second o's target is 'r' — inconsistent.

Test Case 3:

Input:s = "ab", t = "aa"

Output:false

Explanation:a→a and b→a — two different s-characters can't both map to the same t-character.

Constraints

◆1 ≤ s.length ≤ 5 × 10⁴
◆t.length == s.length
◆s and t consist of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (string) — 1-6 lowercase letters, same length as tt (string) — 1-6 lowercase letters, same length as s

1	class Solution {
2	public boolean isIsomorphic(String s, String t) {
3	Map<Character, Character> mapST = new HashMap<>();
4	Map<Character, Character> mapTS = new HashMap<>();
5	for (int i = 0; i < s.length(); i++) {
6	char cs = s.charAt(i);
7	char ct = t.charAt(i);
8	if (mapST.containsKey(cs) && mapST.get(cs) != ct) return false;
9	if (mapTS.containsKey(ct) && mapTS.get(ct) != cs) return false;
10	mapST.put(cs, ct);
11	mapTS.put(ct, cs);
12	}
13	return true;
14	}
15	}
16

String

↑i

String

↑i

HashMap

map.has(e)?

empty

HashMap

empty

Variables

i0

cse

cta

mapST[cs]none

COMPARE

'e' isn't in mapST yet — no conflict possible here.

Step 1 / 10

Approach & Solutions

Brute Force — Compare Every Pair of Positions

Brute

Two strings are isomorphic exactly when, for every pair of positions i and j, s[i] equals s[j] if and only if t[i] equals t[j]. Check every pair directly — if any pair disagrees between s and t, the mapping is broken. Correct, but comparing all n² pairs is quadratic.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public boolean isIsomorphic(String s, String t) {
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                boolean sMatch = s.charAt(i) == s.charAt(j);
                boolean tMatch = t.charAt(i) == t.charAt(j);
                if (sMatch != tMatch) return false;
            }
        }
        return true;
    }
}

Optimal — Two Hash Maps, One Pass

Optimal

Walk both strings together, maintaining two maps: one from each s-character to the t-character it's paired with, and one going the other way. At each position, check both maps for a conflict before recording the pairing — this catches both directions of a broken mapping (two s-characters mapping to the same t-character, or one s-character mapping to two different t-characters) in a single pass.

TimeO(n)