# LeetCode 205：同构字符串 Isomorphic Strings

### 题目：

Given two strings s* and t*, determine if they are isomorphic.

Two strings are isomorphic if the characters in s* can be replaced to get t*.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

```输入: s = "egg", t = "add"

```输入: s = "foo", t = "bar"

```输入: s = "paper", t = "title"

Note: You may assume both s* and t* have the same length.

### 解题思路：

• `s = 'aa' , t = 'ab'`，在建立过字母映射 `a <==> a` 后，s 第二个字母 a 其映射 `value = a` 不等于 t 中第二个字母 b
• `s = 'ab' , t = 'aa'`，在建立过字母映射 `a <==> b` 后，t 第二个字母 a 其映射 `key = a` 不等于 s 中第二个字母 b

```输入：s = 'aa' , t = 'ab'

s中第一个字符 a 第一次出现的索引为0，t中第一个字符 a 第一次出现的索引为0，索引相等，继续遍历

s中第二个字符 a 第一次出现的索引为0，t中第二个字符 b 第一次出现的索引为1，索引不相等， 返回false```

### 代码：

#### 双哈希映射:

Java:

```class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s_map = new HashMap<>();
Map<Character, Character> t_map = new HashMap<>();
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray(); // 转成 cahr 型数组
for (int i = 0; i < s_chars.length; i++) {
// 两种不成立的情况
if (s_map.containsKey(s_chars[i]) && s_map.get(s_chars[i]) != t_chars[i]) return false;
if (t_map.containsKey(t_chars[i]) && t_map.get(t_chars[i]) != s_chars[i]) return false;
s_map.put(s_chars[i], t_chars[i]);
t_map.put(t_chars[i], s_chars[i]);
}
return true;
}
}```

Python:

```class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_map, t_map = {}, {} # 双字典
for c1, c2 in zip(s, t):
# 两种不成立的情况
if c1 in s_map and s_map[c1] != c2:
return False
if c2 in t_map and t_map[c2] != c1:
return False
s_map[c1] = c2
t_map[c2] = c1
return True```

#### 单哈希映射：

Java:

```class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap<>();// 一个哈希映射
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
for (int i = 0; i < s_chars.length; i++) {
if (map.containsKey(s_chars[i]) && map.get(s_chars[i]) != t_chars[i]) return false;
// 判断t中字符是否存在于映射中的 values 内
if (!map.containsKey(s_chars[i]) && map.containsValue(t_chars[i])) return false;
map.put(s_chars[i], t_chars[i]);
}
return true;
}
}```

Python:

```class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
hash_map = {}
for c1, c2 in zip(s, t):
if c1 in hash_map and hash_map[c1] != c2:
return False
# 判断t中字符是否存在于映射中的 values 内
if c1 not in hash_map and c2 in hash_map.values():
return False
hash_map[c1] = c2
return True```

#### 字符首次出现的索引对比法：

Java：

```class Solution {
public boolean isIsomorphic(String s, String t) {
char[] s_chars = s.toCharArray();
char[] t_chars = t.toCharArray();
for (int i = 0; i < s.length(); i++) {
// 判断该字符首次出现索引值是否相等
if (s.indexOf(s_chars[i]) != t.indexOf(t_chars[i])) {
return false;
}
}
return true;
}
}```

Python：

```class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
for c1, c2 in zip(s, t):
# 判断该字符首次出现索引值是否相等
if s.find(c1) != t.find(c2):
return False
return True```

#### 256 位字符映射

Java

```class Solution {
public boolean isIsomorphic(String s, String t) {
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
char[] s_map = new char[256], t_map = new char[256]; //索引与存储值建立映射
for (int i = 0; i < s_chars.length; i++) {
char sc = s_chars[i], tc = t_chars[i];
if (s_map[sc] == 0 && t_map[tc] == 0) {
s_map[sc] = tc;
t_map[tc] = sc;
} else if (s_map[sc] != tc || t_map[tc] != sc) {//索引与元素值的映射是否满足条件
return false;
}
}
return true;
}
}```

python 中没有字符这一基础数据类型。

0 条评论

• ### LeetCode 387: 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

• ### LeetCode 136：只出现一次的数字 Single Number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

• ### LeetCode 652: 寻找重复的子树 Find Duplicate Subtrees

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

• ### iOS 堆栈符号解析最佳实践

本文介绍了如何解析 iOS 的 crash 堆栈，分别使用了 symbolicatecrash 来自动解析整个堆栈，以及使用 atos 来解析单个地址的符号。 ...

• ### Xdebug 攻击面在 PhpStorm 上的现实利用

在调试 Drupal 远程命令执行漏洞（CVE-2018-7600 && CVE-2018-7602）时，存在一个超大的数组 \$form 。在该数组中寻找到注入...

• ### win10 uwp 去掉 Flyout 边框

本文会经常更新，请阅读原文： https://lindexi.gitee.io/post/win10-uwp-%E5%8E%BB%E6%8E%...

• ### Docker常用命令记录

-t 选项是让docker分配一个伪终端（pseudo-tty）并绑定到容器的标准输入上

• ### mysql跨库关联查询（创建视图）

我们使用的场景是：我们使用的是微服务架构，考虑的是模块划分，分为了业务配置服务，基础服务，业务服务等模块，数据库也进行了拆分，不同的模块使用不同的数据库。由于微...