Isomorphic Strings

205. 同构字符串

分析

双向映射：
- 用两个哈希表建立双向映射关系。
  - st：记录从 s 到 t 的映射
  - ts：记录从 t 到 s 的映射
逐字符映射检查：
- 遍历字符串，检查每一对字符是否满足映射规则：
  - 如果 s[i] 已经映射到某个字符，但不是 t[i]，则返回 false
  - 如果 t[i] 已经映射到某个字符，但不是 s[i]，则返回 false
合法映射：
- 如果遍历结束都没有冲突，返回 true

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {
        // 1. 创建两个哈希表：s -> t 和 t -> s
        std::unordered_map<char, char> st, ts;

        // 2. 遍历字符串
        for (int i = 0; i < s.size(); ++i)
        {
            char a = s[i], b = t[i];

            // 3. 检查 s -> t 的映射关系是否冲突
            if (st.count(a) && st[a] != b)
                return false;

            // 4. 建立 s -> t 的映射
            st[a] = b;

            // 5. 检查 t -> s 的映射关系是否冲突
            if (ts.count(b) && ts[b] != a)
                return false;

            // 6. 建立 t -> s 的映射
            ts[b] = a;
        }

        // 7. 映射无冲突，返回 true
        return true;
    }
};