205.同构字符串

发表于： 分类于：
字数： 1187 阅读：≈ 3分钟

🔡 205.同构字符串

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

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

思路

基本思想

要理解题中的两个要求：

  1. 不同字符不能映射到同一字符上，例如"badc"和"baba"就不是同构字符串，因为a映射给了a，后面的c也想映射到a，这是不被允许的，a不能对应两个映射
  2. 相同字符只能映射到同一字符上，例如"add"和"egg"，d只能映射到g，才能满足两个字符串是同构的

并且需要注意，字符串中的元素不全都是字母，也有可能是数字，即"abcd"和"1234"都是字符串，所以记录某个字符是否被记录时，不能使用下面的语句：

1
2

#数组中的每一个位置代表对应的字母是否被映射过了
vector<int> v(26,0)

所以为了完成第一个要求，需要使用一个unordered_set记录已被映射的元素，每次形成新的映射时，都要判断元素是否已经被映射

为了满足条件2，每次都判断是否存在已经建立好的映射，防止相同元素映射到了不同的字符上

所以设置两个容器，分别是unordered_set和unordered_map，前者记录元素是否被映射过，后者记录元素的映射关系

执行流程

  1. 定义两个容器分别记录元素是否被映射和元素的映射关系
  2. 对于字符串中的每个元素，判断是否有映射
    1. 如果有映射，判断映射之后是否与另外一个字符串的对应位置相等，不相等说明不是同构字符串
    2. 如果没有映射，需要新建映射关系，同时还需要注意元素是否已经被映射，防止不同的元素映射到了同一个字符上
  3. 一旦出现映射不匹配或者已经被映射的情况，都返回false，没有上述情况则返回true

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if(s.size()!=t.size())
            return false;
        //使用哈希表记录字符之间的映射关系
        //映射之后查看对应位是否相等，不相等的话直接返回false
        //记录当前元素是不是被占，字符串中不只是字母，还有数字
        unordered_set<char> uset;
        //记录元素之间的映射关系
        unordered_map<char,char> umap;
        for(int i=0;i<s.size();++i){
            //存在映射关系
            if(umap.find(s[i])!=umap.end()){
                //映射之后不相等，直接返回false
                if(umap[s[i]]!=t[i])
                    return false;
            }else{//不存在映射关系，将映射关系加入到unordered_map中
                if(uset.find(t[i])==uset.end()){//当前字符没被映射
                    umap.insert(make_pair(s[i],t[i]));
                    uset.insert(t[i]);//标记当前元素已经被映射
                }else{
                    return false;
                }
            }
        }
        //遍历结束都能映射，此时说明是同构的
        return true;
    }
};

总结

主要有以下几点需要注意：

  1. 字符串中的元素不都是字母，也可能是数字
  2. 不同的元素不能映射到同一字符上
  3. 相同字符只能映射到同一个字符上