← DSA Foundations
easyString Basics

Isomorphic Strings

Two strings are isomorphic when a one-to-one replacement of characters in the first produces the second. Determine whether this is possible.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two nonempty strings on separate lines.

Expected result

true or false.
Case 1

Input

egg
add

Expected output

true
Case 2

Input

foo
bar

Expected output

false
Case 3

Input

ab
aa

Expected output

false

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Isomorphism needs a bijection between characters of s and t; a one-way map misses many-to-one collisions. The strings have equal length and a finite alphabet, so one pass suffices. We keep d_1 and d_2 for s → t and t → s. A conflict with an existing mapping fails; otherwise we update and continue.

We can use two hash tables or arrays d_1 and d_2 to record the character mapping relationship between s and t.

Traverse s and t, if the corresponding character mapping relationships in d_1 and d_2 are different, return false, otherwise update the corresponding character mapping relationships in d_1 and d_2. After the traversal is complete, it means that s and t are isomorphic, and return true.

The time complexity is O(n) and the space complexity is O(C). Where n is the length of the string s; and C is the size of the character set, which is C = 256 in this problem.

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> d1 = new HashMap<>();
        Map<Character, Character> d2 = new HashMap<>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char a = s.charAt(i), b = t.charAt(i);
            if (d1.containsKey(a) && d1.get(a) != b) {
                return false;
            }
            if (d2.containsKey(b) && d2.get(b) != a) {
                return false;
            }
            d1.put(a, b);
            d2.put(b, a);
        }
        return true;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.