205.同构字符串

发表于 更新于 分类于 ，

题目

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

说明: 你可以假设 s 和 t 具有相同的长度。

思路

既然同构的s和t有着一一对应的关系,应该使用泛型字典来存储这样的一一对应关系.

因为我们知道,如果s,和t长度相同却不构成一对一关系,那就只可能是一对多,多对一,多对多关系,所以我们在一个循环之内一定可以判断两者是否同构.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public bool IsIsomorphic(string s, string t)
{
    Dictionary<char, char> strInfo = new Dictionary<char, char>();
    for (int i = 0; i < s.Length; i++)
    {
        if (!strInfo.ContainsKey(s[i]))//如果字典里面没有s[i].
        {
            if (strInfo.ContainsValue(t[i]))//但是已经存在了与之对应的t[i],说明产生了多对一关系.
            {
                return false;
            }
            strInfo.Add(s[i], t[i]);
        }
        else
        {
            if (strInfo[s[i]] != t[i])//如果字典里面已经有了s[i],就看看t[i]是否与之配对.
            {
                return false;
            }
        }
    }
    return true;
}