题目描述

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

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

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

样例

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

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

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

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

算法分析

字符顺序一致，判断每个字符是否一一对应

• 1、用哈希表st维护s字符串中字符与t字符串中字符的对应关系;ts维护t字符串中字符与s字符串中字符的对应关系
• 2、枚举字符串s和t中的所有字符，判断s当前字符a和t当前字符b是否一一对应
  • (1)若已经存在对应关系，但不对应则返回false
  • (2)若不存在对应关系，则新建对应关系

时间复杂度 $O(n)$

Java 代码

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> st = new HashMap<Character, Character>();
        HashMap<Character, Character> ts = new HashMap<Character, Character>();
        for(int i = 0;i < s.length();i ++)
        {
            char a = s.charAt(i), b = t.charAt(i);
            if(st.containsKey(a) && st.get(a) != b) return false;
            if(ts.containsKey(b) && ts.get(b) != a) return false;

            if(!st.containsKey(a) && !ts.containsKey(b) ) 
            {
                st.put(a, b);
                ts.put(b, a);
            }
        }
        return true;
    }
}