| 链接 | 同构字符串 |
|---|---|
| 题序号 | 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) {//两个字符串长度不一样，直接返回 falseif (s.length() != t.length()) return false;//使用两个哈希表来检查双向映射，确保一一对应的关系unordered_map<char, char> mapST; // 映射 s -> tunordered_map<char, char> mapTS; // 映射 t -> sfor (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，//说明映射冲突，两个字符串无法是同构的，直接返回 falseif (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) {//两个字符串长度不一样，直接返回 falseif (s.length() != t.length()) return false;//使用两个哈希表来检查双向映射，确保一一对应的关系unordered_map<char, char> mapST; // 映射 s -> tunordered_map<char, char> mapTS; // 映射 t -> sfor (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，//说明映射冲突，两个字符串无法是同构的，直接返回 falseif (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;
}
