205. 同构字符串
题目描述
输入两个长度相同的字符串 s 和 t。判断能否把 s 中的字符逐个替换，得到 t。能则称两者同构，返回 true，否则返回 false。
替换要遵守一套固定的对应规则：同一个字符每次都换成同一个字符；两个不同的字符不能换成同一个字符；字符可以对应它自己。替换不改变字符的位置。
示例 1
输入：s = "egg", t = "add" 输出：true
解释：令 'e' 对应 'a'、'g' 对应 'd' 即可。
示例 2
输入：s = "foo", t = "bar" 输出：false
解释：'o' 在 t 中需要同时对应 'a' 和 'r'，不可能。
示例 3
输入：s = "paper", t = "title" 输出：true
解释：p→t、a→i、e→l、r→e 是一套合法的对应关系。
数据范围
1 <= s.length <= 5 * 10^4t.length == s.lengths和t由合法的 ASCII 字符组成。
解题思路
同构要求映射是双射，所以用两张表：st 记录 s 的字符映射到 t 的哪个字符，ts 记录反方向。逐对扫描 (a, b)：如果 st 里 a 已经映射到别的字符，或者 ts 里 b 已经被别的字符占用，就冲突返回 false；否则记下这对映射。
为什么正确
处理完前 i 对字符后，st 和 ts 互为逆映射，且前缀 s[:i] 经 st 替换后恰好等于 t[:i]。
复杂度分析
时间 O(n)；空间 O(|Σ|)，Σ 为字符集。
易错点
只用一张 s→t 的表不够：s="ab", t="aa" 时 a→a、b→a 各自不冲突，但两个字符映射到了同一个字符，必须用反向表 ts 拦住。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
st, ts = {}, {}
for a, b in zip(s, t):
if st.get(a, b) != b or ts.get(b, a) != a:
return False
st[a] = b
ts[b] = a
return Trueclass Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> st = new HashMap<>(), ts = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i), b = t.charAt(i);
if (st.getOrDefault(a, b) != b || ts.getOrDefault(b, a) != a) {
return false;
}
st.put(a, b);
ts.put(b, a);
}
return true;
}
}class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char, char> st, ts;
for (size_t i = 0; i < s.size(); i++) {
char a = s[i], b = t[i];
if ((st.count(a) && st[a] != b) || (ts.count(b) && ts[b] != a)) {
return false;
}
st[a] = b;
ts[b] = a;
}
return true;
}
};func isIsomorphic(s string, t string) bool {
st, ts := map[byte]byte{}, map[byte]byte{}
for i := 0; i < len(s); i++ {
a, b := s[i], t[i]
if v, ok := st[a]; ok && v != b {
return false
}
if v, ok := ts[b]; ok && v != a {
return false
}
st[a] = b
ts[b] = a
}
return true
}var isIsomorphic = function(s, t) {
const st = new Map(), ts = new Map();
for (let i = 0; i < s.length; i++) {
const a = s[i], b = t[i];
if ((st.has(a) && st.get(a) !== b) || (ts.has(b) && ts.get(b) !== a)) {
return false;
}
st.set(a, b);
ts.set(b, a);
}
return true;
};function isIsomorphic(s: string, t: string): boolean {
const st = new Map<string, string>(), ts = new Map<string, string>();
for (let i = 0; i < s.length; i++) {
const a = s[i], b = t[i];
if ((st.has(a) && st.get(a) !== b) || (ts.has(b) && ts.get(b) !== a)) {
return false;
}
st.set(a, b);
ts.set(b, a);
}
return true;
}