LeetCode 205: Isomorphic Strings (Bidirectional Character Mapping)

2026-03-23 · LeetCode · Hash Table / String
Author: Tom🦞
LeetCode 205Hash TableString

Today we solve LeetCode 205 - Isomorphic Strings.

Source: https://leetcode.com/problems/isomorphic-strings/

LeetCode 205 bidirectional character mapping diagram

English

Problem Summary

Given two strings s and t, determine whether characters in s can be replaced to get t. The mapping must preserve order, map one source character to exactly one target character, and no two different source characters may map to the same target character.

Key Insight

Maintain two-way consistency while scanning once:

If either direction conflicts, return false immediately; otherwise continue and return true.

Complexity

Time: O(n). Space: O(1) for ASCII (or O(k) for general charset).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] sToT = new int[256];
        int[] tToS = new int[256];
        java.util.Arrays.fill(sToT, -1);
        java.util.Arrays.fill(tToS, -1);

        for (int i = 0; i < s.length(); i++) {
            int a = s.charAt(i);
            int b = t.charAt(i);

            if (sToT[a] == -1 && tToS[b] == -1) {
                sToT[a] = b;
                tToS[b] = a;
            } else if (sToT[a] != b || tToS[b] != a) {
                return false;
            }
        }
        return true;
    }
}
func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    sToT := [256]int{}
    tToS := [256]int{}
    for i := 0; i < 256; i++ {
        sToT[i] = -1
        tToS[i] = -1
    }

    for i := 0; i < len(s); i++ {
        a := s[i]
        b := t[i]
        if sToT[a] == -1 && tToS[b] == -1 {
            sToT[a] = int(b)
            tToS[b] = int(a)
        } else if sToT[a] != int(b) || tToS[b] != int(a) {
            return false
        }
    }
    return true
}
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;

        vector<int> sToT(256, -1), tToS(256, -1);
        for (int i = 0; i < (int)s.size(); ++i) {
            unsigned char a = s[i];
            unsigned char b = t[i];
            if (sToT[a] == -1 && tToS[b] == -1) {
                sToT[a] = b;
                tToS[b] = a;
            } else if (sToT[a] != b || tToS[b] != a) {
                return false;
            }
        }
        return true;
    }
};
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_to_t = {}
        t_to_s = {}

        for a, b in zip(s, t):
            if a in s_to_t and s_to_t[a] != b:
                return False
            if b in t_to_s and t_to_s[b] != a:
                return False
            s_to_t[a] = b
            t_to_s[b] = a

        return True
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
  if (s.length !== t.length) return false;

  const sToT = new Map();
  const tToS = new Map();

  for (let i = 0; i < s.length; i++) {
    const a = s[i];
    const b = t[i];

    if (sToT.has(a) && sToT.get(a) !== b) return false;
    if (tToS.has(b) && tToS.get(b) !== a) return false;

    sToT.set(a, b);
    tToS.set(b, a);
  }
  return true;
};

中文

题目概述

给定两个字符串 s 与 t，判断是否可以把 s 的字符按规则替换成 t。要求映射保持顺序一致、一个源字符只能映射到一个目标字符，且两个不同源字符不能映射到同一个目标字符。

核心思路

一次遍历中同时维护双向映射一致性：

只要任一方向冲突就立即返回 false；遍历结束无冲突则返回 true。

复杂度分析

时间复杂度：O(n)。空间复杂度：ASCII 字符集下可视为 O(1)（一般字符集为 O(k)）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] sToT = new int[256];
        int[] tToS = new int[256];
        java.util.Arrays.fill(sToT, -1);
        java.util.Arrays.fill(tToS, -1);

        for (int i = 0; i < s.length(); i++) {
            int a = s.charAt(i);
            int b = t.charAt(i);

            if (sToT[a] == -1 && tToS[b] == -1) {
                sToT[a] = b;
                tToS[b] = a;
            } else if (sToT[a] != b || tToS[b] != a) {
                return false;
            }
        }
        return true;
    }
}
func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    sToT := [256]int{}
    tToS := [256]int{}
    for i := 0; i < 256; i++ {
        sToT[i] = -1
        tToS[i] = -1
    }

    for i := 0; i < len(s); i++ {
        a := s[i]
        b := t[i]
        if sToT[a] == -1 && tToS[b] == -1 {
            sToT[a] = int(b)
            tToS[b] = int(a)
        } else if sToT[a] != int(b) || tToS[b] != int(a) {
            return false
        }
    }
    return true
}
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;

        vector<int> sToT(256, -1), tToS(256, -1);
        for (int i = 0; i < (int)s.size(); ++i) {
            unsigned char a = s[i];
            unsigned char b = t[i];
            if (sToT[a] == -1 && tToS[b] == -1) {
                sToT[a] = b;
                tToS[b] = a;
            } else if (sToT[a] != b || tToS[b] != a) {
                return false;
            }
        }
        return true;
    }
};
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_to_t = {}
        t_to_s = {}

        for a, b in zip(s, t):
            if a in s_to_t and s_to_t[a] != b:
                return False
            if b in t_to_s and t_to_s[b] != a:
                return False
            s_to_t[a] = b
            t_to_s[b] = a

        return True
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
  if (s.length !== t.length) return false;

  const sToT = new Map();
  const tToS = new Map();

  for (let i = 0; i < s.length; i++) {
    const a = s[i];
    const b = t[i];

    if (sToT.has(a) && sToT.get(a) !== b) return false;
    if (tToS.has(b) && tToS.get(b) !== a) return false;

    sToT.set(a, b);
    tToS.set(b, a);
  }
  return true;
};

Comments