0205. Isomorphic Strings
========================
题目信息
--------
:题号: 0205. 同构字符串
:难度: Easy
:主题: 字符串、双射、双向映射
:原题: `LeetCode 0205 `_
:重点: 同一源字符映射一致、不同源字符不能共享目标,两个方向必须同时检查
题目重述
--------
给定两个字符串 ``s`` 和 ``t``,判断是否可以把 ``s`` 中的每一种字符统一替换成某个字符,
使结果恰好等于 ``t``。同一个源字符的所有出现位置必须映射到同一个目标字符;两个不同源字符
不能映射到同一个目标字符;字符允许映射到自身。
``s`` 和 ``t`` 的长度相同,长度位于 ``[1, 5 * 10^4]``,字符为有效 ASCII 字符。判断的是
对应位置的模式关系,不是字符频次或字典序;函数只返回布尔值,不修改输入字符串。
自建示例
--------
重复位置模式一致:
.. code-block:: text
输入:s = "egg",t = "add"
输出:true
解释:e->a,g->d;g 的两次出现都映射到 d。
同一个源字符被迫映射到两个目标:
.. code-block:: text
输入:s = "foo",t = "bar"
输出:false
解释:o 第一次要映射到 a,第二次又要映射到 r,不能由一个统一替换完成。
不同源字符争用同一个目标:
.. code-block:: text
输入:s = "ab",t = "aa"
输出:false
解释:a 和 b 都需要映射到 a,违反目标字符不能重复占用。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
public:
bool isIsomorphic(std::string s, std::string t) {
return checkWithBidirectionalMap(s, t);
}
private:
bool checkWithBidirectionalMap(const std::string& s, const std::string& t) {
if (s.size() != t.size()) return false;
std::array sourceToTarget;
std::array targetToSource;
sourceToTarget.fill(-1);
targetToSource.fill(-1);
for (std::size_t index = 0; index < s.size(); ++index) {
unsigned char source = static_cast(s[index]);
unsigned char target = static_cast(t[index]);
if ((sourceToTarget[source] != -1 && sourceToTarget[source] != target) ||
(targetToSource[target] != -1 && targetToSource[target] != source)) {
return false;
}
sourceToTarget[source] = target;
targetToSource[target] = source;
}
return true;
}
bool checkByPreviousPositions(const std::string& s, const std::string& t) {
if (s.size() != t.size()) return false;
std::array lastSource;
std::array lastTarget;
lastSource.fill(0);
lastTarget.fill(0);
for (std::size_t index = 0; index < s.size(); ++index) {
unsigned char source = static_cast(s[index]);
unsigned char target = static_cast(t[index]);
if (lastSource[source] != lastTarget[target]) return false;
lastSource[source] = static_cast(index) + 1;
lastTarget[target] = static_cast(index) + 1;
}
return true;
}
};
题解
----
逐位置建立替换关系
~~~~~~~~~~~~~~~~~~~~
字符串替换不是为每个位置临时挑一个字符,而是为每个源字符建立一次统一规则。最直接的搜索
是扫描对应位置 ``(s[i], t[i])``,把它解释为一条 ``s[i] -> t[i]`` 关系;之后遇到同一个源
字符时,必须复用已经登记的目标。
但只保存 ``source -> target`` 还不够。例如 ``s = "ab"``、``t = "aa"`` 时,单向表可以先
登记 ``a->a``,再登记 ``b->a``,看不出两个来源占用了同一个目标。合法替换要求的是双射:
既要保证源字符的函数一致性,也要保证目标字符最多有一个来源。
双向映射把冲突变成局部检查
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
维护两张互逆表:
.. code-block:: text
sourceToTarget[source] = target
targetToSource[target] = source
处理当前字符对 ``source = s[i]``、``target = t[i]`` 时,先检查两种冲突:若源字符已有目标,
它必须仍等于当前目标;若目标字符已有来源,来源必须仍等于当前源。两项都通过时才写入两张
表;新字符对扩展映射,重复字符对只是再次确认已有事实。
这样每个位置只需常数次数组访问,不必枚举字符替换方案,也不必在后续位置重新搜索前缀。
双向表记录的正是当前前缀已经确定的部分,局部冲突一旦出现就足以拒绝整个字符串。
状态不变量
~~~~~~~~~~~~
扫描到位置 ``index`` 之前,保持:
* 对所有已处理位置,``sourceToTarget[s[i]] == t[i]``;
* ``targetToSource`` 恰好记录同一批关系的反方向;
* 一个源字符至多有一个目标,一个目标字符至多有一个来源;
* 两张表互为逆关系,已登记的配对构成部分双射;
* ``index`` 及之后的字符尚未影响映射。
当前字符对若与任一既有关系冲突,任何后续替换都无法修复已经矛盾的前缀;若无冲突,同时写入
两张表后,不变量继续成立。扫描结束意味着每个位置都满足同一个双射,因此可以返回 ``true``。
状态走读
~~~~~~~~
对 ``s = "egg"``、``t = "add"``:
.. list-table::
:header-rows: 1
* - 位置
- 字符对
- 新状态
- 结果
* - 0
- ``e,a``
- ``e->a``、``a->e``
- 建立第一对关系
* - 1
- ``g,d``
- ``g->d``、``d->g``
- 建立第二对关系
* - 2
- ``g,d``
- 状态不变
- 与既有关系一致
对 ``s = "ab"``、``t = "aa"``,位置 0 建立 ``a<->a``;位置 1 的源 ``b`` 尚未出现,但目标
``a`` 已由源 ``a`` 占用,反向表立即报告冲突。对 ``foo`` 与 ``bar``,位置 2 的源 ``o`` 已经
映射到 ``a``,而当前目标是 ``r``,正向表报告冲突。两个失败位置展示了两张表各自不可替代的
职责。
按出现位置记录模式
~~~~~~~~~~~~~~~~~~~~
``checkByPreviousPositions`` 是同一判定的另一种表达。对每个字符记录它上一次出现的位置,
未出现用 ``0`` 表示。扫描位置 ``index`` 时,若 ``s[index]`` 与 ``t[index]`` 的上次出现位置
不同,说明两个字符串的重复模式已经分叉;若相同,就把两者都更新为当前的 ``index + 1``。
例如 ``egg`` 与 ``add`` 在三个位置的上次出现位置分别为 ``(0,0)``、``(0,0)``、``(2,2)``,
模式一致。这个版本不直接保存字符到字符的映射,代码更短,但需要读者先接受“同构等价于每个
位置的上次出现模式相同”;主入口选择双向映射,因为它直接对应题目的替换规则。
代码分析
~~~~~~~~
公共入口调用 ``checkWithBidirectionalMap``,用 256 项数组覆盖有效 ASCII。数组初值 ``-1`` 表示
尚未见过;字符先转成 ``unsigned char`` 再作为下标,避免把有符号 ``char`` 当作负数索引。
代码在写入前同时检查正向和反向关系。长度检查也必须先于按位置访问;虽然题目保证长度相同,
保留该分支使函数契约在独立阅读时完整。重复配对可以重复赋同样的值,不会改变已经成立的不变量。
``checkByPreviousPositions`` 用 ``index + 1`` 区分“从未出现”的 0 与第 0 个位置,并将双向
映射压缩成两个位置状态。它不是第三种本质不同的算法,而是为了展示从显式映射到位置模式的
等价转换;两者都不修改输入字符串。
复杂度与边界
~~~~~~~~~~~~
两种方法都扫描每个字符一次,时间复杂度为 ``O(n)``。双向数组和位置数组各有 256 个槽位,
额外空间为 ``O(1)``;若改用哈希表,空间则按实际不同字符数计为 ``O(k)``。长度不同立即返回
``false``;空字符串虽不在题目约束中,长度相等时也会自然返回 ``true``。
字符映射到自身不需要特殊分支,重复字符只要关系一致即可继续。ASCII 范围使固定数组下标有界,
不会出现因 Unicode 多字节编码而改变题目字符单位的额外语义。