205.同构字符串

题目

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

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

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

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

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

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

简单来说，同构的意思是结构相同。即若s和t是同构的，那么：

• s如果是ABB的结构，t也必须是ABB的结构
• s如果是AABB的结构，t也必须是AABB的结构
• 以此类推

方法（用哈希表）

准备一个哈希表。用于将s中的一个字符映射到t中的一个字符。

算法步骤：

• 遍历s中的每一个字符
• 如果s中的一个字符还未入哈希表（之前未出现过），但t中该位置的元素已作为value处在哈希表中（之前出现过），说明不同构，返回false。否则将该字符作为key，t中同位置的字符作为value，将这对(key, value)入哈希表。
• 如果s中的一个字符已经存在于哈希表中，那么就检查该字符在哈希表中的value值于t中同位置的字符是否相同，如果不同，说明s和t结构不同，直接返回false

代码

public static boolean isIsomorphic(String s, String t) {
    HashMap<Character, Character> map = new HashMap<>();
    char[] sChar = s.toCharArray();
    char[] tChar = t.toCharArray();
    for(int i = 0; i < s.length(); i++){
        if(!map.containsKey(sChar[i])){
            //如果s中该位置元素之前未出现过，但是t中该位置元素已出现过
            //说明s和t不不同构，返回false。例如"ab"和"aa"
            if(map.containsValue(tChar[i]))
                return false;
            map.put(sChar[i], tChar[i]);
        }
        else {
            if (map.get(sChar[i]) != tChar[i])
                return false;
        }
    }
    return true;
}