leetcode 面试经典 150 题：同构字符串
| 链接 | 同构字符串 |
|---|---|
| 题序号 | 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 字符组成
哈希表
-
哈希表：是一种以键值对（key-value）形式存储数据的数据结构，它通过哈希函数将键映射到特定的位置（索引），从而实现高效的查找、插入和删除操作。
-
在 C++ 中，常用的哈希表容器是
std::unordered_map。 -
哈希表的特点
- 高效性：哈希表的查找、插入和删除操作的平均时间复杂度是 O(1)。这是通过哈希函数直接定位到元素所在的位置实现的。
- 非有序性：哈希表中的元素存储顺序通常和插入顺序不同，具体取决于哈希函数。如果需要有序的键值对，可以使用 std::map。
- 冲突处理：当两个键经过哈希函数映射到相同的位置时，称为哈希冲突。哈希表通过链地址法（链表）或开放地址法（探测）解决冲突。
-
c++ 示例：
#include <unordered_map>
#include <iostream>
using namespace std;
int main() {
// 定义一个哈希表
unordered_map<string, int> myMap;
// 插入键值对
myMap["apple"] = 5;
myMap["banana"] = 3;
myMap["cherry"] = 8;
// 访问值
cout << "apple: " << myMap["apple"] << endl; //输出 5
// 查找键是否存在
if (myMap.count("banana")) {
cout << "banana exists, value: " << myMap["banana"] << endl; //存在，输出值为 3
}
// 删除键值对
myMap.erase("cherry");
// 遍历哈希表
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl; //输出 apple 和 banana 的键值对
}
return 0;
}
题解
- 核心要点：使用哈希表（HashMap）来存储字符之间的映射关系。遍历字符串s和t的每个字符，建立字符的映射关系。如果s中的字符已经存在于映射中，并且对应的映射不是当前字符t中的字符，则返回false。如果t中的字符已经存在于映射中，并且对应的映射不是当前字符s中的字符，则返回false。否则，建立字符之间的映射关系。
- 复杂度：时间复杂度为
O(n)，其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s 和 t 即可；空间复杂度为O(字符串的字符集)。 - c++ 实现算法：
bool isIsomorphic(string s, string t) {
//两个字符串长度不一样，直接返回 false
if (s.length() != t.length()) return false;
//使用两个哈希表来检查双向映射，确保一一对应的关系
unordered_map<char, char> mapST; // 映射 s -> t
unordered_map<char, char> mapTS; // 映射 t -> s
for (int i = 0; i < s.length(); i++) {
char sChar = s[i];
char tChar = t[i];
// 检查 s -> t 的映射是否一致
//检查字符 sChar 是否已经在 mapST 中有记录
if (mapST.count(sChar)) {
//如果 mapST 中记录的 sChar 的映射值不是当前的 tChar，
//说明映射冲突，两个字符串无法是同构的，直接返回 false
if (mapST[sChar] != tChar) return false;
} else {
//如果 sChar 尚未在 mapST 中建立映射，就将当前的 sChar -> tChar 关系存入映射表中。
mapST[sChar] = tChar;
}
// 检查 t -> s 的映射是否一致
if (mapTS.count(tChar)) {
if (mapTS[tChar] != sChar) return false;
} else {
mapTS[tChar] = sChar;
}
}
return true;
}
- 算法演示：
示例
输入：s = “egg”, t = “add”
- 第一轮 (sChar = ‘e’, tChar = ‘a’)
mapST 为空，sChar = ‘e’ 不在 mapST 中。
建立映射：mapST[‘e’] = ‘a’。- 第二轮 (sChar =‘g’, tChar = ‘d’)
sChar = ‘g’ 不在 mapST 中。
建立映射：mapST[‘g’] = ‘d’。- 第三轮 (sChar = ‘g’, tChar = ‘d’)
sChar = ‘g’ 在 mapST 中，且 mapST[‘g’] == ‘d’，符合映射，继续。 返回 true，两个字符串是同构的。反例 s = “foo”, t = “bar”
- 第一轮 (sChar = ‘f’, tChar = ‘b’)
建立映射：mapST[‘f’] = ‘b’。- 第二轮 (sChar = ‘o’, tChar = ‘a’)
建立映射：mapST[‘o’] = ‘a’。- 第三轮 (sChar = ‘o’, tChar = ‘r’)
sChar = ‘o’ 在 mapST 中，但 mapST[‘o’] != ‘r’。 返回 false。
- c++ 完整demo：
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
bool isIsomorphic(string s, string t) {
//两个字符串长度不一样，直接返回 false
if (s.length() != t.length()) return false;
//使用两个哈希表来检查双向映射，确保一一对应的关系
unordered_map<char, char> mapST; // 映射 s -> t
unordered_map<char, char> mapTS; // 映射 t -> s
for (int i = 0; i < s.length(); i++) {
char sChar = s[i];
char tChar = t[i];
// 检查 s -> t 的映射是否一致
//检查字符 sChar 是否已经在 mapST 中有记录
if (mapST.count(sChar)) {
//如果 mapST 中记录的 sChar 的映射值不是当前的 tChar，
//说明映射冲突，两个字符串无法是同构的，直接返回 false
if (mapST[sChar] != tChar) return false;
} else {
//如果 sChar 尚未在 mapST 中建立映射，就将当前的 sChar -> tChar 关系存入映射表中。
mapST[sChar] = tChar;
}
// 检查 t -> s 的映射是否一致
if (mapTS.count(tChar)) {
if (mapTS[tChar] != sChar) return false;
} else {
mapTS[tChar] = sChar;
}
}
return true;
}
int main() {
string s = "egg";
string t = "add";
cout << (isIsomorphic(s, t) ? "true" : "false") << endl;
s = "foo";
t = "bar";
cout << (isIsomorphic(s, t) ? "true" : "false") << endl;
s = "paper";
t = "title";
cout << (isIsomorphic(s, t) ? "true" : "false") << endl;
return 0;
}