力扣面试经典——205题

💡 参考代码：

/**
 * 判断两个字符串是否同构
 * 
 * @param s 字符串s
 * @param t 字符串t
 * @return bool true表示同构，false表示不同构
 * 
 * 解题思路：
 * 1. 建立两个映射表，分别记录s->t和t->s的字符映射关系
 * 2. 遍历字符串，检查映射关系是否一致
 * 3. 若发现冲突则返回false，遍历完成则返回true
 * 
 * 时间复杂度：O(n)，其中n为字符串长度
 * 空间复杂度：O(1)，使用固定大小的数组作为哈希表
 */
bool isIsomorphic(char * s, char * t){
    // 边界条件检查
    if (s == NULL || t == NULL) {
        return false;
    }
    
    int len_s = strlen(s);
    int len_t = strlen(t);
    
    // 长度不等直接返回false
    if (len_s != len_t) {
        return false;
    }
    
    // 创建两个映射表，ASCII字符范围为0-127
    int map_s_to_t[128] = {0};  // 记录s到t的字符映射
    int map_t_to_s[128] = {0};  // 记录t到s的字符映射
    
    // 初始化映射表为-1，表示尚未建立映射关系
    for (int i = 0; i < 128; i++) {
        map_s_to_t[i] = -1;
        map_t_to_s[i] = -1;
    }
    
    // 遍历字符串建立和验证映射关系
    for (int i = 0; i < len_s; i++) {
        char char_s = s[i];
        char char_t = t[i];
        
        // 检查s到t的映射
        if (map_s_to_t[char_s] == -1) {
            // 尚未建立映射，建立新映射
            map_s_to_t[char_s] = char_t;
        } else if (map_s_to_t[char_s] != char_t) {
            // 已存在映射但与当前字符不匹配，返回false
            return false;
        }
        
        // 检查t到s的映射
        if (map_t_to_s[char_t] == -1) {
            // 尚未建立映射，建立新映射
            map_t_to_s[char_t] = char_s;
        } else if (map_t_to_s[char_t] != char_s) {
            // 已存在映射但与当前字符不匹配，返回false
            return false;
        }
    }
    
    // 所有字符映射关系一致，返回true
    return true;
}

📖 总结：

点击展开题目总结

🤔 同构字符串

---

1️⃣ 题目核心信息

🎯 功能描述：判断两个字符串是否同构，即字符串中字符之间能否建立一一对应的映射关系

📥 输入输出：

• 输入：两个字符串 s 和 t
• 输出：布尔值，表示两个字符串是否同构

---

2️⃣ 实现原理

💡 核心思路：使用哈希表建立双向字符映射关系，确保映射的一一对应性

📋 实现步骤：

1. 检查输入字符串的有效性和长度一致性
2. 创建两个哈希表分别记录 s→t 和 t→s 的字符映射关系
3. 遍历字符串，对每一对字符检查并建立映射关系
4. 发现映射冲突时返回 false，遍历完成返回 true

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用固定大小数组模拟哈希表，提高访问效率
• 双向映射检查确保一一对应关系
• 初始化为-1表示未建立映射，避免与ASCII码值0冲突

4️⃣ 使用场景

✅ 适用情况：

• 字符串模式匹配问题
• 字符映射关系验证
• 密码学中的简单替换密码验证

⚠️ 前提条件：

• 输入为有效的ASCII字符串
• 两个字符串长度必须相等

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中 n 为字符串长度，只需遍历一次字符串

• 💾 空间复杂度：O(1)，使用固定大小的数组(128个元素)作为哈希表

6️⃣ 注意事项

🚩 边界情况：

• 输入为空指针
• 字符串长度不相等
• 空字符串情况

💥 易错点：

• 忘记检查双向映射导致映射不唯一
• 哈希表初始化值与有效ASCII码冲突
• 没有正确处理字符到数组索引的转换

7️⃣ 补充说明

以 s = "paper" 和 t = "title" 为例：

执行步骤详解

// 输入: s = "paper", t = "title"
// 期望输出: true

bool isIsomorphic(char * s, char * t) {
    // 1. 初始化阶段
    // len_s = 5, len_t = 5 (长度相等，继续执行)
    
    // map_s_to_t[128] = {-1, -1, ..., -1}  // 所有元素初始化为-1
    // map_t_to_s[128] = {-1, -1, ..., -1}  // 所有元素初始化为-1
    
    // 2. 逐字符检查映射关系
    // i = 0: s[0]='p', t[0]='t'
    // map_s_to_t['p'] == -1 → 建立映射: map_s_to_t['p'] = 't'
    // map_t_to_s['t'] == -1 → 建立映射: map_t_to_s['t'] = 'p'
    
    // i = 1: s[1]='a', t[1]='i'
    // map_s_to_t['a'] == -1 → 建立映射: map_s_to_t['a'] = 'i'
    // map_t_to_s['i'] == -1 → 建立映射: map_t_to_s['i'] = 'a'
    
    // i = 2: s[2]='p', t[2]='t'
    // map_s_to_t['p'] == 't' → 映射一致，继续
    // map_t_to_s['t'] == 'p' → 映射一致，继续
    
    // i = 3: s[3]='e', t[3]='l'
    // map_s_to_t['e'] == -1 → 建立映射: map_s_to_t['e'] = 'l'
    // map_t_to_s['l'] == -1 → 建立映射: map_t_to_s['l'] = 'e'
    
    // i = 4: s[4]='r', t[4]='e'
    // map_s_to_t['r'] == -1 → 建立映射: map_s_to_t['r'] = 'e'
    // map_t_to_s['e'] == -1 → 建立映射: map_t_to_s['e'] = 'r'
    
    // 3. 所有字符检查完成，未发现冲突
    // 返回 true
}

映射关系总结

执行完成后建立的映射关系：

• s→t 映射: p→t, a→i, e→l, r→e
• t→s 映射: t→p, i→a, l→e, e→r 这个映射是一一对应的，每个字符都有唯一的映射目标，因此函数返回 true。

对比例子

如果输入是 s = "foo", t = "bar"：

• i=0: f→b, b→f
• i=1: o→a, a→o
• i=2: o→r，但之前 o 已映射到 a，冲突！ 此时 map_s_to_t['o'] != 'r'，函数返回 false。

加载评论中...