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.
For example,
Given “egg”, “add”, return true.
Given “foo”, “bar”, return false.
Given “paper”, “title”, return true.
Note:
You may assume both s and t have the same length.
最初的思路和290. Word Pattern差不多，只是把字符串s当做那道题中的字符串pattern，而把字符串t当做那道题中的str即可，建立从s到t的一个映射，之后排除掉一些需要返回false的情况即可，代码如下:
/*solution1,use two unordered_map,24ms*/
class Solution {
public:
bool isIsomorphic(string s, string t) {
if(s.size()!=t.size())
return false;
unordered_map<char,char> hash;
int i=0;
for(i=0;i<s.size();i++){
if(hash.find(s[i])!=hash.end()){
if(hash[s[i]]!=t[i])
return false;
}
else{
for(unordered_map<char,char>::iterator it=hash.begin();it!=hash.end();it++){
if(it->second==t[i])
return false;
}
hash[s[i]]=t[i];
}
}
return i==s.size();
}
};
可以看出，两道题的代码极其相似，由于用了两个哈希表，所以运行时间较长，那么我们考虑到这道题给出的测试样例中应该都是 ASCII编码的字符，于是我们可以运用之前学到的使用数组代替哈希表的技巧来优化这个算法。代码如下:
/*solution2,use two arrays,8ms*/
class Solution {
public:
bool isIsomorphic(string s, string t) {
int map1[256]={0},map2[256]={0},i=0;/*数组要初始化为0*/
for(i=0;i<s.size();i++){
if(map1[s[i]]!=map2[t[i]])/*如果s中的字符映射之后和t中字符映射之后不相等，则返回false;
首次进入循环时，两个字符映射之后的值都为0，所以不会返回false*/
return false;
map1[s[i]]=map2[t[i]]=i+1;/*否则将其更新为同一个值*/
}
return i==s.size();
}
};
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。