205. Isomorphic Strings

问题

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Note:
You may assume both s and t have the same length.

例子

Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

分析

isomorphic的意思是“同构”。如果t的s的同构，给定一个下标i，si-->ti的映射关系必须唯一，即不存在一个si映射到两个ti，也不存在两个si映射到一个ti。同构关系就是下图中的双射：

映射

• 方法一：使用一个map，一个set。同时遍历s和t，map保存s和t当前字符的映射关系，set保存t的当前字符。新的映射关系sc-->tc要满足sc在map的键中不存在，而且tc在set中不存在。

• 方法二：使用两个128大小的数组，分别保存s和t字符出现的最新遍历次数。如果s和t当前字符的最新遍历次数不同，即说明t不是s的同构。

要点

• 理解同构的概念；
• bucket思想。

时间复杂度

O(n)

空间复杂度

O(1)

代码

方法一

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> umap;
        unordered_set<char> uset;
        for (int i = 0; i < s.length(); i++) {
            if (umap.find(s[i]) == umap.end())
            {
                if (uset.find(t[i]) != uset.end())
                    return false;
                umap[s[i]] = t[i];
                uset.insert(t[i]);
            }
            else if (umap[s[i]] != t[i])
                return false;
        }
        return true;
    }
};

方法二

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int smap[128] = {0}, tmap[128] = {0};
        for (int i = 0; i < s.length(); i++) {
            if (smap[s[i]] != tmap[t[i]]) return false;
            smap[s[i]] = i + 1;
            tmap[t[i]] = i + 1;
        }
        return true;
    }
};