Isomorphic Strings

Problem#

Given two strings s and t, return true iff a bijective mapping exists between s’s characters and t’s characters that preserves order — i.e., f(s[i]) = t[i] for all i and f is one-to-one.

Examples#

s = "egg", t = "add" → true (e->a, g->d).
s = "foo", t = "bar" → false (o would map to both a and r).
s = "paper", t = "title" → true.

Constraints#

1 <= s.length <= 5 * 10^4, ASCII characters.

Hints#

Hint

Track both directions: s[i] -> t[i] and t[i] -> s[i]. A conflict on either side is failure.

Approach#

Two parallel maps (or int[256] arrays). On each index check existing mapping; mismatch returns false. If neither side is mapped, assign both.

Solution#

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        int s2t[256] = {0}, t2s[256] = {0};
        for (int i = 0; i < (int)s.size(); ++i) {
            unsigned char a = s[i], b = t[i];
            if (s2t[a] == 0 && t2s[b] == 0) {
                s2t[a] = b;
                t2s[b] = a;
            } else if (s2t[a] != b || t2s[b] != a) {
                return false;
            }
        }
        return true;
    }
};

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    var s2t, t2s [256]byte
    for i := 0; i < len(s); i++ {
        a, b := s[i], t[i]
        if s2t[a] == 0 && t2s[b] == 0 {
            s2t[a] = b
            t2s[b] = a
        } else if s2t[a] != b || t2s[b] != a {
            return false
        }
    }
    return true
}

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        s2t: dict = {}
        t2s: dict = {}
        for a, b in zip(s, t):
            if a not in s2t and b not in t2s:
                s2t[a] = b
                t2s[b] = a
            elif s2t.get(a) != b or t2s.get(b) != a:
                return False
        return True

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    const s2t = new Map(), t2s = new Map();
    for (let i = 0; i < s.length; i++) {
        const a = s[i], b = t[i];
        if (!s2t.has(a) && !t2s.has(b)) {
            s2t.set(a, b);
            t2s.set(b, a);
        } else if (s2t.get(a) !== b || t2s.get(b) !== a) {
            return false;
        }
    }
    return true;
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] s2t = new int[256];
        int[] t2s = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            if (s2t[a] == 0 && t2s[b] == 0) {
                s2t[a] = b;
                t2s[b] = a;
            } else if (s2t[a] != b || t2s[b] != a) {
                return false;
            }
        }
        return true;
    }
}

function isIsomorphic(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    const s2t: Map<string, string> = new Map();
    const t2s: Map<string, string> = new Map();
    for (let i = 0; i < s.length; i++) {
        const a = s[i], b = t[i];
        if (!s2t.has(a) && !t2s.has(b)) {
            s2t.set(a, b);
            t2s.set(b, a);
        } else if (s2t.get(a) !== b || t2s.get(b) !== a) {
            return false;
        }
    }
    return true;
}

Editorial#

Both-direction tracking is essential — a single-direction map would accept "ab" -> "aa" (a maps to a, b maps to a, but a would already be the image of a). The arrays default-zero is fine here because all valid ASCII characters are >= 1; if zero could be a real value, use sentinel -1 instead.

Complexity#

Time: O(N).
Space: O(1) — fixed 256-byte arrays.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#