205. 同构字符串

题目描述:给定两个字符串 s 和 t,判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

难度:简单

例子:

输入: s = "egg", t = "add"
输出: true

输入: s = "abba", t = "abab"
输出: false

输入: s = "", t = ""
输出: true

int haha(char *str, int *code, int *val) {
    
    int len = strlen(str);
    int ans = 1;
    while (len > 0) {
        code[str[len - 1]] += 1;
        if (val[str[len - 1]] == 0) {// 测序
            val[str[len - 1]] = ans;
            ans += 1;
        }
        len -= 1;
    }
    int cnt = 0;
    for (int i = 0; i < 300; i++) {
        if(code[i]) cnt += code[i];//测公共长度
    }
    return cnt;
}

bool isIsomorphic(char* s, char* t) {
    int code1[300] = {0}, code2[300] = {0};
    int val1[300] = {0}, val2[300] = {0};
    int s_cnt = haha(s, code1, val1);
    int t_cnt = haha(t, code2, val2);
    if (s_cnt == t_cnt) {
        for (int i = 0; s[i]; i++) {
            if (code1[s[i]] == code2[t[i]] && val1[s[i]] == val2[t[i]]) continue;// 公共大小和测序能直接判断两个字符串是否满足替换规则
            return false;
        }
    }
    return s_cnt == t_cnt;
}

如果没有测序,只有公共大小部分,那么
A = |a|b|b|a|
B = |a|b|a|b|
|2|2|2|2|(公共长度)
然而测序为:
A : |1|2|2|1|
B : |1|2|1|2|
所以两者能确定是否存在替换规则,这种问题不需要考虑用什么(字符)来替换。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。