如何判断两个字符串是否同构？现有C++逻辑存在问题需排查

嘿，我一眼就看出你代码里的问题啦！你的思路只考虑了第一个字符串到第二个字符串的单向映射一致性，但完全漏掉了同构定义要求的双向唯一映射——也就是说，不仅input1里的每个字符要固定对应input2里的某个字符，反过来input2里的每个字符也只能被input1里的一个字符对应。

为什么你的测试用例会失效？ #

拿你测试的"abcd"和"aabb"来说：

• input1的a对应input2的a，input1的b也对应input2的a——这就出现了两个不同的input1字符映射到同一个input2字符的情况，这根本不符合同构的定义。
• 你的diff_arr只记录了input1每个字符对应的差值，完全没检查input2的字符是否被重复映射了，所以代码错误地返回了true。

怎么修复这个问题？ #

你需要额外维护一个数组（或者哈希表）来记录input2字符对应的映射，确保每个input2字符只能被一个input1字符映射。这里给你修改后的代码示例：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool is_isomorphic(string input1, string input2) {
    if(input1.length()!= input2.length()) 
        return false;
    // 记录input1字符到input2字符的映射（用索引代替字符）
    vector<int> map1(26, -1);
    // 记录input2字符到input1字符的映射
    vector<int> map2(26, -1);
    
    for(int i = 0 ; i < input1.length(); i++){
        int c1 = input1[i] - 'a';
        int c2 = input2[i] - 'a';
        
        // 如果两个字符都还没建立映射
        if(map1[c1] == -1 && map2[c2] == -1){
            map1[c1] = c2;
            map2[c2] = c1;
        } else {
            // 检查双向映射是否一致，不一致则不是同构
            if(map1[c1] != c2 || map2[c2] != c1){
                return false;
            }
        }
    }
    return true;
}

int main() {
    cout << boolalpha << is_isomorphic("abcd", "aabb") << endl; // 现在会输出false，符合预期
    return 0;
}

修复后的逻辑说明 #

修改后的代码同时维护了双向映射：

1. 当遍历到一对字符时，如果两者都没建立映射，就互相记录对方的索引。
2. 如果其中任意一个已经有映射，就检查当前的字符对是否和已有的映射一致，不一致直接返回false。

这样就能避免像你之前那样的单向映射漏洞，确保符合同构字符串的严格定义。

内容的提问来源于stack exchange，提问作者user11281642