双哈希映射
为什么要用两个哈希表呢?
因为在s中’a’映射t的’b’,而t的’b’可以映射s的’c’
- 首先判断字符串长度是否相等
- 同时遍历两个字符串
- s[i]存在ms中,并且s[i]对应的t[i]不相等,返回false
- t[i]存在mt中,并且t[i]对应的s[i]不相等,返回false
- s[i]和t[i]都不存在ms和mt中,插入哈希表
- 遍历完,说明没问题,返回true
时间复杂度 $O(N)$,空间复杂度$O(N)$
AC代码
class Solution {
public:
bool isIsomorphic(string s, string t) {
int n = s.size(), m = t.size();
if (n != m) return false;
if (!n) return true;
unordered_map<char,char> ms, mt;
for (int i = 0 ; i < n ; i ++) {
if (ms.count(s[i]) && ms[s[i]] != t[i])
return false;
if (mt.count(t[i]) && mt[t[i]] != s[i])
return false;
if (!ms.count(s[i]) && !mt.count(t[i])){
ms[s[i]] = t[i];
mt[t[i]] = s[i];
}
}
return true;
}
};