跳到主要内容

LeetCode 205. 同构字符串

本节目标

用双向映射验证两个等长字符串是否保持一一字符对应关系。

这道题对应单词与映射解题框架的双向映射模型。每个 s 中的字符要稳定映射到 t 中一个字符，同时不同源字符不能汇聚到同一个目标字符。

查看原题

朴素思路及瓶颈​

朴素做法可对每个位置回看所有此前位置，检查“相等关系是否一致”，最坏为 O(n²)。映射把每种字符的历史约束压缩成常数次查表，因此一次扫描就能发现冲突。

双向映射不变量​

在处理第 i 对字符前，正向表记录每个已见 s 字符唯一对应的 t 字符，反向表记录相反关系。若正向不一致，说明一个源字符映射到了两个目标；若反向不一致，说明多个源字符映射到了同一目标。只检查正向表会错误接受 badc -> baba 这类多对一关系。

代码实现​

C++ 以两个 256 位数组表示字节范围内的双向映射；Python 用两张字典。实现先检查长度，再对每一对字符检查并同步更新两张表。

C++17
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }

        vector<int> forward(256, -1);
        vector<int> backward(256, -1);
        for (size_t index = 0; index < s.size(); index++) {
            unsigned char from = static_cast<unsigned char>(s[index]);
            unsigned char to = static_cast<unsigned char>(t[index]);
            if ((forward[from] != -1 && forward[from] != to) ||
                (backward[to] != -1 && backward[to] != from)) {
                return false;
            }
            forward[from] = to;
            backward[to] = from;
        }
        return true;
    }
};

复杂度分析​

  • 时间复杂度：O(n)。
  • 空间复杂度：C++ 为 O(1) 的固定数组，Python 最坏为 O(k)，k 是不同字符数。

易错点​

  • 只保存 s -> t，漏掉两个不同字符占用同一个目标字符。
  • 字符串长度不同仍按最短长度配对，误把未处理尾部忽略。
  • 冲突发生后直接覆盖映射，而没有立即返回失败。

模式迁移​

同构判断可迁移到替换密码、模板变量和节点标签的对应检查。若只需判断重复出现的位置模式，也可记录每个符号上次出现的索引并比较索引模式。