leetcode 205 同构字符串

zhaojun

2022 年 08 月 30 日

2451 次浏览

暂无评论

447字数

默认分类

# [205. 同构字符串](https://leetcode.cn/problems/isomorphic-strings/)

## 题目

给定两个字符串 `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).

```java
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)

```java
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)：

```java
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;
    }
}
```

最后修改：2022 年 08 月 30 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 205 同构字符串

zhaojun • 2022 年 08 月 30 日

leetcode 205 同构字符串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

leetcode 1769 移动所有球到每个盒子所需的最小操作数

Shiro 学习 04 - 加密

Spring 使用事件监听来解耦代码

日志输出最佳实践

debian 11 vps 安装 pve7

leetcode 205 同构字符串

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 205 同构字符串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款