LeetCode 力扣 205. 同构字符串

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

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

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

示例 1:

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

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

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

思路

hash表解决单方向的映射问题,即只能保证从多对多变成多对一,因此需要翻转两次hash表才行

code

class Solution {
public:
//hash只能 解决单方向的映射问题,即只能保证从多对多变成
// 多对一,因此要来两边才行
    bool isIsomorphic(string s, string t) {
        //方法1:用hash记录映射关系
        //方法2:用数组hash来记录映射关系
        unordered_map<char,char> umap;
        if(s.size() != t.size()){
            return false;
        }
        for(int i = 0 ;i < s.size() ; i ++){
            if(umap.find(s[i]) == umap.end()){
                umap.insert(make_pair(s[i],t[i]));
            }else{
                if(umap[s[i]] != t[i]){
                    return false;
                }
            }
        }
        umap.clear();
        swap(s,t);
                for(int i = 0 ;i < s.size() ; i ++){
            if(umap.find(s[i]) == umap.end()){
                umap.insert(make_pair(s[i],t[i]));
            }else{
                if(umap[s[i]] != t[i]){
                    return false;
                }
            }
        }
        return true;
    }
};

本文由博客一文多发平台 OpenWrite 发布!

热门相关:最强狂兵   薄先生,情不由己   寂静王冠   霸皇纪   霸皇纪