2019-11-15 同构字符串

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

说明:

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

失败

C++1

首先想到使用hash表，分别用两个hash表存入两个字符串中不同元素的数量，然后转出到vector中，最后排序比较不同元素的数目是否分布是一样的。后来发现没考虑顺序信息，比如"egg"和"ada"，最后结果都是122，但是这是错误的，应该是122和212。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, int> hm;
        for (int i=0; i<s.length(); ++i)
        {
            if(hm.count(s[i])<=0){
                hm.insert(make_pair(s[i], 1));
            }else{
                hm[s[i]]=hm[s[i]]+1;
            }
        }
        unordered_map<char, int> hm2;
        for (int j=0; j<t.length(); ++j)
        {
            if(hm2.count(t[j])<=0){
                hm2.insert(make_pair(t[j], 1));
            }else{
                hm2[t[j]]=hm2[t[j]]+1;
            }
        }
        vector<int> v1,v2;
        for ( auto& x: hm ){
            v1.push_back(x.second);
        }
        for ( auto& x2: hm2 ){
            v2.push_back(x2.second);
        }
        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());
        for(int y:v1){
            cout << y;
        }
        cout << endl;
        for(int x:v2){
            cout << x;
        }
        if(v1.size() == v2.size())
        {
            for(vector<int>::const_iterator p = v1.begin(),q = v2.begin(); p!= v1.end(); p++,q++)
            {
                if(*p != *q)
                {
                    return false;
                }
            }
            return true;
        }
        return false;

C++2

这次是按照index索引计算的，分别计算得出每个索引位置的元素对应的出现次数，这次"abba"和"abab"都是2222了，但是这其实也是不对的，false，还是因为顺序不对。第一个是中间两位相同，第二个字符串是相隔一位相同。

我太难了。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, int> hm;
        for (int i=0; i<s.length(); ++i)
        {
            if(hm.count(s[i])<=0){
                hm.insert(make_pair(s[i], 1));
            }else{
                hm[s[i]]=hm[s[i]]+1;
            }
        }
        unordered_map<int, int> hm3;
        unordered_map<int, int> hm4;
        for (int i=0; i<s.length(); ++i)
        {
            hm3[i]=hm[s[i]];
        }
        
        unordered_map<char, int> hm2;
        for (int j=0; j<t.length(); ++j)
        {
            if(hm2.count(t[j])<=0){
                hm2.insert(make_pair(t[j], 1));
            }else{
                hm2[t[j]]=hm2[t[j]]+1;
            }
        }
        for (int i=0; i<t.length(); ++i)
        {
            hm4[i]=hm2[t[i]];
        }
        
        
        vector<int> v1,v2;
        for ( auto& x: hm3 ){
            v1.push_back(x.second);
        }
        for ( auto& x2: hm4 ){
            v2.push_back(x2.second);
        }
        for(int y:v1){
            cout << y;
        }
        cout << endl;
        for(int x:v2){
            cout << x;
        }
        if(v1.size() == v2.size())
        {
            for(vector<int>::const_iterator p = v1.begin(),q = v2.begin(); p!= v1.end(); p++,q++)
            {
                if(*p != *q)
                {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};

成功

C++3

class Solution {
public:
    bool isIsomorphic(string s, string t) { 
        vector<int> vecS(256,-1),vecT(256,-1);
        for(int i=0;i<s.length();i++){
            if(vecS[s[i]]!=vecT[t[i]]){return false;}
            vecS[s[i]] = vecT[t[i]] = i;
        }
        return true;
    }
};

差得多啊qaq