问题
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;
}
};
