题目描述:
给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
示例 1:
输入: s ="egg",
t ="add"
输出: true
示例 2:
输入: s ="foo",
t ="bar"
输出: false
示例 3:
输入: s ="paper",
t ="title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
思路:
根据题目的意思,只要满足 从 t 到 s 是双射,也就是 s 与 t 中元素一一对应。
其实,只要 s->t 和 t->s 都是单射就可以了。那用一个数组来保存映射,由于ASCII码表上使用的符号是128个,所以数组大小定为128;又因为0是作为字符串结束符不计算在字符串内的,不用映射,所以用0作为初值表示尚未填写映射。
bool isIsomorphic(string s, string t) {
//0 代表没有填写过映射值。
int fs[128]={0};//保存映射s->t
int ft[128]={0};//保存映射t->s
int temp;
//需要保证t[i]->s[i] 以及s[i]->t[i]都是唯一的
for(int i=0;i<t.size();i++)
{
//尚未映射过,则添加映射
if(fs[s[i]]==0 && ft[t[i]]==0)
{
fs[s[i]]=t[i];
ft[t[i]]=s[i];
}
//都映射过了
else if(fs[s[i]]&&ft[t[i]])
{
//不是双向的单射
if(fs[s[i]]!=t[i] || ft[t[i]]!=s[i])
return false;
}
//有一个映射过,一个没有映射,没有映射的话肯定不是单射
else return false;
}
//全部映射成功
return true;
}
算法时间复杂度 O(n),空间复杂度 O(1),测试运行时间 12ms。
在上面代码中,else if 和下面的 else做的其实是同一件事情:判断是否存在双向的单射。所以可以把它们合并,代码改写为:
bool isIsomorphic(string s, string t) {
//0 代表没有填写过映射值。
int fs[128]={0};//保存映射s->t
int ft[128]={0};//保存映射t->s
//需要保证t[i]->s[i] 以及s[i]->t[i]都是唯一的
for(int i=0;i<t.size();i++)
{
//尚未映射过,则添加映射
if(fs[s[i]]==0 && ft[t[i]]==0)
{
fs[s[i]]=t[i];
ft[t[i]]=s[i];
}
//映射过,判断是否存在双向的单射
else if(fs[s[i]]!=t[i] || ft[t[i]]!=s[i])
return false;
}
//全部映射成功
return true;
}
时间复杂度 O(n),空间复杂度 O(1),测试运行时间 4ms。可见循环体中的语句对时间的影响很大!
看了以下其它效率高的算法,他们思路跟我差不多,但也有不同之处。我是在两个字符集合之间映射,然后判断是不是双方都是单射;他们则引入了第三个集合:整数集,把两个字符集都映射到整数集,然后判断相同位置的字符是不是映射到同一个整数。并且中间有一些巧妙的处理,使得代码更简洁了。
bool isIsomorphic(string s, string t) {
//初值0
vector<int> num1(256, 0), num2(256, 0);
int length = s.size();
for (int i = 0; i < length; i++) {
//下面三行代码,免去了判断“是否已经映射过”
//不管是否映射过,如果两个字符映射到不同的整数,那肯定不对。
if (num1[s[i]] != num2[t[i]]) return false;
//不管是否映射过,把它们的映射值都改为同一个整数
//必须改,因为没有对0的判断。并且i+1之前没有被映射过,一定不会引发矛盾。
num1[s[i]] = i + 1;
num2[t[i]] = i + 1;
}
return true;
}
时间复杂度也是 O(n),空间复杂度也是 O(1)。
;