205. 同构字符串

题目

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

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

题解1

自己想的解法，就是一个 map，存储映射关系，循环遍历每个元素，分别设 s 和 t 的每个元素为 a 和 b

• 如果映射表里 key 中不包含 a，且 value 中不包含 b，则写入映射表。
• 如果映射表里 key 中包含 a，则将映射值赋值为 a，并比较是否一致，如果不一致，直接返回 false。
• 如果映射表里 key 中不包含 a，但 value 中包含 b，则说明 a 之前映射为 b，现在又映射成其他的了，直接返回 false。

时间复杂度 O(n)，空间复杂度 O(n).

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> mapping = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            char b = t.charAt(i);
    
            if (mapping.containsKey(a)) {
                if (mapping.get(a) != b) {
                    return false;
                }
            } else if (mapping.containsValue(b)) {
                return false;
            } else {
                mapping.put(a, b);
                continue;
            }

        }

        return true;
    }
}

题解 2

这个题解是在评论区找的，非常简洁的代码，另人敬佩。

思路就是，获取当前元素所在的第一个 index 是否一样，如果不一样，则说明一定有某一个元素映射此处超过 1 次。精妙绝伦。 因每次都要 indexOf 从头遍历找，故时间复杂度为 O(n²)（实际情况没有这么差，且可以利用缓存避免每次都查），空间复杂度 O(1)

class Solution {
    public boolean isIsomorphic(String s, String t) {
          for(int i = 0; i < s.length(); i++){
              if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){
                  return false;
              }
          }  
          return true;
    }
}

题解 3

对题解 2 优化后（缓存了 index）时间复杂度 O(n)，空间复杂度 O(1)：

class Solution {
    public boolean isIsomorphic(String s, String t) {
      int[] cnt1 = new int[127];
      int[] cnt2 = new int[127];
      for(int i = 0; i < s.length(); i++) {
        char a = s.charAt(i);
        char b = t.charAt(i);
        int aa = cnt1[a];
        int bb = cnt2[b];

        if (aa == 0 && bb == 0) {
          cnt1[a] = i;
          cnt2[b] = i;
          aa = s.indexOf(a);
          bb = t.indexOf(b);
        }
        if (aa != bb) {
          return false;
        }
      }
      return true;
    }
}