字符同构

by ·0 Comments

原题链接：http://www.lintcode.com/zh-cn/problem/strings-homomorphism/
给定两个字符串 s 和 t ，确定它们是否是同构的。
两个字符串是同构的如果 s 中的字符可以被替换得到 t。
所有出现的字符必须用另一个字符代替，同时保留字符串的顺序。 没有两个字符可以映射到同一个字符，但一个字符可以映射到自己。

样例
给出 s = “egg”, t= “add”, 返回 true。
给出 s = “foo”, t= “bar”, 返回 false。
给出 s = “paper”, t= “title”, 返回 true。

思路：由“映射”比较容易想到字典。可以由s到t逐位建立字符到字符之间的键值对，如果某个键第二次出现，则立刻去字典中检验此键对应的值是不是t中第二次出现的值。假如不是，则可以立刻返回False。在字典建立完毕后，再统计字典的值中有没有相同的元素，如果有，说明有一个值可以对应两个键，也不满足条件，直接return False。如果运行完毕没有问题，说明键值对存在一一对应的关系，return True即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    """
    @param: s: a string
    @param: t: a string
    @return: true if the characters in s can be replaced to get t or false
    """
    def isIsomorphic(self, s, t):
        if s == '' or t =='' or len(s)!=len(t):
            return False
        mapped = {}
        for i in range(len(s)):
            if s[i] not in mapped:
                mapped[s[i]] = t[i]
            else:
                if mapped[s[i]] != t[i]:
                    return False
        if len(mapped.values()) != len(set(mapped.values())):
            return False
        return True