(LeetCode 面试经典 150 题) 205. 同构字符串 (哈希表)

题目：205. 同构字符串

思路：哈希表，时间复杂度0(n)。
用两个哈希表分别记录各种对应的字符即可，细节看注释。

C++版本：

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char,char> mps,mpt;
        int n=s.size();
        for(int i=0;i<n;i++){
        	// 两个哈希表都没有记录，说明没有匹配过
            if(mpt.find(t[i])==mpt.end()&& mps.find(s[i])==mps.end()){
                mpt[t[i]]=s[i];
                mps[s[i]]=t[i];
            }else{
            	// 其中一个有匹配过，不对应就false
                if(mpt.find(t[i])!=mpt.end()){
                    if(mpt[t[i]]!=s[i]) return false;
                }
                if(mps.find(s[i])!=mps.end()){
                    if(mps[s[i]]!=t[i]) return false;
                }
            }
        }
        return true;
    }
};

JAVA版本：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> mps= new HashMap<>();
        Map<Character,Character> mpt= new HashMap<>();
        int n=s.length();
        for(int i=0;i<n;i++){
            char a=s.charAt(i),b=t.charAt(i);
            if(mpt.containsKey(b)==false && mps.containsKey(a)==false){
                mpt.put(b,a);
                mps.put(a,b);
            }else{
                if(mps.containsKey(a)&&mps.get(a)!=b) return false;
                if(mpt.containsKey(b)&&mpt.get(b)!=a) return false;
            }
        }
        return true;
    }
}

GO版本：

func isIsomorphic(s string, t string) bool {
    mps:=map[byte]byte{}
    mpt:=map[byte]byte{}
    n:=len(s)
    for i:=0;i<n;i++ {
        if mps[s[i]]==0 &&mpt[t[i]]==0 {
            mps[s[i]]=t[i]
            mpt[t[i]]=s[i]
        }else{
            if mps[s[i]]>0 &&mps[s[i]]!=t[i] {
                return false
            }
            if mpt[t[i]]>0 &&mpt[t[i]]!=s[i] {
                return false
            }
        }
    }
    return true;
}