leetcode 205. 同构字符串

题目描述:

给定两个字符串 和 t,判断它们是否是同构的。

如果 中的字符可以被替换得到 ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明:
你可以假设 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)。

;