Isomorphic Strings

2017/12/20 posted in  leetcode

一开始写的代码,超时版本,用的集合。

bool isIsomorphic(string s, string t) {
    unordered_map<char, set<int>> Smap;
    unordered_map<char, vector<int>> Tmap;
    for (int i = 0; i<s.size(); i++) {
        Smap[s[i]].insert(i);
        Tmap[t[i]].push_back(i);
    }
    if (Smap.size()!=Tmap.size()) {
        return 0;
    }else{
        for (int j = 0; j<s.size(); j++) {
            vector<int> a = Tmap[t[j]];
            set<int> b = Smap[s[j]];
            int len = b.size();
            for (auto num : a) {
                b.insert(num);
                if (len!=b.size()) {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}

修改后的版本。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;  //判断两个字符串i位置的字符上次出现的位置是否一样。
            m1[s[i]] = i + 1;   //记录上次该字符出现的位置
            m2[t[i]] = i + 1;   //记录上次该字符出现的位置
        }
        return true;
    }
};