题目描述（简单难度）

判断两个字符串是否是同构的。

解法一

题目描述中已经很详细了，两个字符串同构的含义就是字符串 可以唯一的映射到 t ，同时 t 也可以唯一的映射到 s 。

举个具体的例子。

我们可以利用一个 map 来处理映射。对于 s 到 t 的映射，我们同时遍历 s 和 t ，假设当前遇到的字母分别是 c1 和 c2 。

如果 map[c1] 不存在，那么就将 c1 映射到 c2 ，即 map[c1] = c2。

如果 map[c1] 存在，那么就判断 map[c1] 是否等于 c2，也就是验证之前的映射和当前的字母是否相同。

  1. private boolean isIsomorphicHelper(String s, String t) {
  2.     int n = s.length();
  3.     HashMap<Character, Character> map = new HashMap<>();
  4.     for (int i = 0; i < n; i++) {
  5.         char c1 = s.charAt(i);
  6.         char c2 = s.charAt(i);
  7.         if (map.containsKey(c1)) {
  8.             if (map.get(c1) != c2) {
  9.                 return false;
  10.             }
  11.         } else {
  12.             map.put(c1, c2);
  13.         }
  14.     }
  15.     return true;
  16. }

对于这道题，我们只需要验证 s - > t 和 两个方向即可。如果验证一个方向，是不可以的。

举个例子，s = ab, t = cc，如果单看 s -> t ，那么 a -> c, b -> c 是没有问题的。

代码的话，只需要调用两次上边的代码即可。

解法二

另一种思想，参考 这里 。

解法一中，我们判断 s 和 t 是否一一对应，通过对两个方向分别考虑来解决的。

这里的话，我们找一个第三方来解决，即，按照字母出现的顺序，把两个字符串都映射到另一个集合中。

举个现实生活中的例子，一个人说中文，一个人说法语，怎么判断他们说的是一个意思呢？把中文翻译成英语，把法语也翻译成英语，然后看最后的英语是否相同即可。

  1. 将第一个出现的字母映射成 1，第二个出现的字母映射成 2
  3. 对于 egg
  4. e -> 1
  5. 也就是将 egg 的 e 换成 1, g 换成 2, 就变成了 122
  7. 对于 add
  8. a -> 1
  9. d -> 2
  10. 也就是将 add 的 a 换成 1, d 换成 2, 就变成了 122
  12. egg -> 122, add -> 122
  13. 都变成了 122，所以两个字符串异构。

代码的话，只需要将两个字符串分别翻译成第三种类型即可。我们可以定义一个变量 count = 1，映射给出现的字母，然后进行自增。

为了方便，我们也可以将当前字母直接映射为当前字母的下标加 1。因为 0 是我们的默认值，所以不能直接赋值为下标，而是「下标加 1」。

  1. public boolean isIsomorphic(String s, String t) {
  2.     return isIsomorphicHelper(s).equals(isIsomorphicHelper(t));
  3. }
  5. private String isIsomorphicHelper(String s) {
  6.     int[] map = new int[128];
  7.     int n = s.length();
  8.     StringBuilder sb = new StringBuilder();
  9.     for (int i = 0; i < n; i++) {
  11.         //当前字母第一次出现,赋值
  12.         if (map[c] == 0) {
  13.             map[c] = i + 1;
  14.         }
  15.     }
  16.     return sb.toString();
  17. }

上边的 isIsomorphicHelper 中我们通过 map 记录了当前字母要映射到哪个数字，然后最终返回了整个转换后的字符串。

举个例子。

代码的话，用两个 map 记录映射即可。

  1. public boolean isIsomorphic(String s, String t) {
  2.     int n = s.length();
  3.     int[] mapS = new int[128];
  4.     int[] mapT = new int[128];
  5.     for (int i = 0; i < n; i++) {
  6.         char c1 = s.charAt(i);
  7.         char c2 = t.charAt(i);
  8.         //当前的映射值是否相同
  9.         if (mapS[c1] != mapT[c2]) {
  10.             return false;
  11.         } else {
  12.             //是否已经修改过，修改过就不需要再处理
  13.             if (mapS[c1] == 0) {
  14.                 mapS[c1] = i + 1;
  15.                 mapT[c2] = i + 1;
  16.             }
  17.         }
  18.     }
  19.     return true;
  20. }

总

解法一就是我们比较常规的思路，解法二通过一个第三方的集合，将代码大大简化了，太巧妙了！

题目其实有点像映射的知识，两个字符串为两个集合，然后判断当前映射是否为单射。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情