知识点

哈希表

思路

如果两个字符串不一样长,则是不可以的。从左到右依次匹配s的字母和t的字母,同时用哈希表记录s的字母和t的字母的对应关系,以及t中被占用的字母。在匹配过程中出现矛盾则返回“NO”。

时间复杂度 O(n)

AC Code(C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return string字符串
     */
    string isIsomorphic(string s, string t) {
        int n = s.size(), m = t.size();
        if (m != n) return "NO";
        unordered_map<char, char> mp;
        unordered_set<char> seen;
        for (int i = 0; i < n; i ++) {
            if (mp.count(s[i])) {
                if (mp[s[i]] != t[i]) return "NO";
                continue;
            }
            if (seen.count(t[i])) return "NO";
            mp[s[i]] = t[i];
            seen.insert(t[i]);
        }
        return "YES";
    }
};