Easy

题目描述

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true
解释：
字符串 s 和 t 可以通过以下映射关系变得相同：
将 'e' 映射到 'a'。
将 'g' 映射到 'd'。

示例 2:

输入：s = "f11", t = "b23"
输出：false
解释：
字符串 s 和 t 不能变得相同，因为 '1' 需要同时映射到 '2' 和 '3'。

示例 3:

输入：s = "paper", t = "title"
输出：true

提示:

  • 1 <= s.length <= 5 * 10⁴
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成。

解题思路

解题思路

这是一道经典的字符映射问题。两个字符串同构的条件是：字符串 s 中的每个字符都能一一对应地映射到字符串 t 中的字符，且这种映射关系是双向唯一的。

核心思路：

  1. 双向映射检查：需要同时维护两个映射关系

    • s 到 t 的映射：确保 s 中相同字符总是映射到 t 中相同字符
    • t 到 s 的映射：确保 t 中不同字符不会被 s 中不同字符映射到

  2. 具体实现：

    • 使用两个哈希表分别记录 s→t 和 t→s 的映射
    • 遍历字符串，对每对字符 (s[i], t[i]) 检查：
      • 如果 s[i] 已有映射且映射值不是 t[i]，返回 false
      • 如果 t[i] 已有映射且映射值不是 s[i]，返回 false
      • 否则建立新的双向映射关系

  3. 优化方案：也可以使用数组代替哈希表，因为题目限定是 ASCII 字符，直接用字符的 ASCII 值作为索引。

推荐解法：双哈希表法，代码简洁且易于理解。

代码实现

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s_to_t, t_to_s;
        
        for (int i = 0; i < s.length(); i++) {
            char c1 = s[i], c2 = t[i];
            
            if (s_to_t.count(c1) && s_to_t[c1] != c2) return false;
            if (t_to_s.count(c2) && t_to_s[c2] != c1) return false;
            
            s_to_t[c1] = c2;
            t_to_s[c2] = c1;
        }
        
        return true;
    }
};

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t = {}
        t_to_s = {}
        
        for c1, c2 in zip(s, t):
            if c1 in s_to_t and s_to_t[c1] != c2:
                return False
            if c2 in t_to_s and t_to_s[c2] != c1:
                return False
            
            s_to_t[c1] = c2
            t_to_s[c2] = c1
        
        return True

public class Solution {
    public bool IsIsomorphic(string s, string t) {
        var sToT = new Dictionary<char, char>();
        var tToS = new Dictionary<char, char>();
        
        for (int i = 0; i < s.Length; i++) {
            char c1 = s[i], c2 = t[i];
            
            if (sToT.ContainsKey(c1) && sToT[c1] != c2) return false;
            if (tToS.ContainsKey(c2) && tToS[c2] != c1) return false;
            
            sToT[c1] = c2;
            tToS[c2] = c1;
        }
        
        return true;
    }
}

var isIsomorphic = function(s, t) {
    const sToT = new Map();
    const tToS = new Map();
    
    for (let i = 0; i < s.length; i++) {
        const c1 = s[i], c2 = t[i];
        
        if (sToT.has(c1) && sToT.get(c1) !== c2) return false;
        if (tToS.has(c2) && tToS.get(c2) !== c1) return false;
        
        sToT.set(c1, c2);
        tToS.set(c2, c1);
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n)只需遍历一次字符串，每次哈希表操作为 O(1)
空间复杂度O(k)k 为字符集大小，最坏情况下需要存储所有不同字符的映射关系

相关题目