leetcode刷题日记——同构字符串
[ 题目描述 ]：
[ 思路 ]：
- 题目要求判断 s 和 t 是否为同构字符串，即 s 中每个字符与 t 中对应位置的字符形成一个映射关系，且只能是一对一映射
- ASCII（American Standard Code for Information Interchange）码是最基础的字符编码标准，用7位二进制数（共128个字符）表示英文字母、数字、符号和控制字符。
- 其中 0-31 是控制字符，32-126 是可打印字符，127 是删除控制符(DEL)，128-255 是扩展 ASCII
- 那么其中有效的 ASCII 字符是 32-126，总共有95个有有效字符
- 那么可以申请一个 95 大小的字符数组用作存储映射关系的映射表，下标表示其自身的值，存储的值表示在映射到数组 t 中的值
- 每遇见一个映射表中不存在的映射关系，添加映射
- 当映射存在，且映射关系与映射表中不同时，说明不是同构字符
- 然后再从 t → s 执行一遍，来检测同一字符是否有多重映射
- 运行如下
bool isIsomorphic(char* s, char* t) {int s_len=strlen(s),t_len=strlen(t);if(s_len!=t_len) return false;char s_t[95]={};char t_s[95]={};for(int i=0;i<s_len;i++){if(s_t[s[i]-32]==NULL){s_t[s[i]-32]=t[i];}else{if(s_t[s[i]-32]!=t[i]) return false;}if(t_s[t[i]-32]==NULL){t_s[t[i]-32]=s[i];}else{if(t_s[t[i]-32]!=s[i]) return false;}}return true;
}
[ 官方题解 ]：
- 方法一：哈希表，通过 hash 表来实现存储关系映射
struct HashTable {char key;char val;UT_hash_handle hh;
};bool isIsomorphic(char* s, char* t) {struct HashTable* s2t = NULL;struct HashTable* t2s = NULL;int len = strlen(s);for (int i = 0; i < len; ++i) {char x = s[i], y = t[i];struct HashTable *tmp1, *tmp2;HASH_FIND(hh, s2t, &x, sizeof(char), tmp1);HASH_FIND(hh, t2s, &y, sizeof(char), tmp2);if (tmp1 != NULL) {if (tmp1->val != y) {return false;}} else {tmp1 = malloc(sizeof(struct HashTable));tmp1->key = x;tmp1->val = y;HASH_ADD(hh, s2t, key, sizeof(char), tmp1);}if (tmp2 != NULL) {if (tmp2->val != x) {return false;}} else {tmp2 = malloc(sizeof(struct HashTable));tmp2->key = y;tmp2->val = x;HASH_ADD(hh, t2s, key, sizeof(char), tmp2);}}return true;
}