💬 Discord
Sign In
NeetCode #44LC-205EasyArrays & Hashing
← Back to All Problems

#44 · #205 · Isomorphic Strings(同构字符串)

📌 Problem Statement & Constraints

Given two strings s and t, determine if they are isomorphic: every character of s can be replaced to get t, with a consistent one-to-one mapping and no two characters mapping to the same character. Constraints: 1 <= s.length <= 5 * 10^4, len(s) == len(t).

💡 Core Algorithmic Approaches

  1. Isomorphism requires a bijection, so two maps are needed: one from s to t and one from t to s.
  2. A single forward map is not enough -- it would allow two different characters of s to map to the same character of t, which is forbidden.
  3. For each position, check the forward map: if s[i] already maps to a different character, fail. Check the reverse map likewise.
  4. Then record both mappings and continue. Different lengths fail immediately.

💻 Benchmark Python3 Implementation

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        fwd = {}                           # s char -> t char
        rev = {}                           # t char -> s char
        for a, b in zip(s, t):
            if fwd.get(a, b) != b or rev.get(b, a) != a:
                return False               # inconsistent mapping
            fwd[a] = b
            rev[b] = a
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) hash operations per character.
💾 Space Complexity
O(k) for the two maps, where k is the size of the character set (at most 26 here, but the approach handles any alphabet).

⚠️ Interview Pitfalls & Follow-ups

  • Using only the forward map: s = "ab", t = "aa" would be wrongly accepted, since both a and b map to a.
  • Comparing character frequency patterns only: the pattern must align position by position, so a frequency comparison is insufficient.
  • Forgetting the length check: zip silently truncates to the shorter string, so unequal lengths must be rejected explicitly.
  • Using fwd.get(a) != b without a default: a missing key returns None, which happens to differ from b, so it works -- but the explicit fwd.get(a, b) form makes the intent clearer.