C++实现判断两个字符串是否同构的代码结果错误，求错误原因分析

Hey, let's break down the issue with your code!

Right now, you're only comparing the frequency of each character in the two strings—but that's not enough to determine if they're isomorphic. Isomorphism requires a bidirectional one-to-one mapping between characters, not just that each character shows up the same number of times.

A Quick Counterexample #

Take s = "abba" and t = "abab" for instance. Both have two as and two bs, so your code would return true. But these strings aren't isomorphic:

• In s, the first a maps to a in t, and the first b maps to b in t.
• But then the third character in s is b, which would need to map to a in t—conflicting with the earlier b->b mapping.
• This breaks the one-to-one rule, so they shouldn't be considered isomorphic.

What's Wrong With Your Logic? #

Your frequency check ensures the two strings have the same character count distribution, but it doesn't account for the order and mapping consistency of characters. Isomorphic strings need:

1. Every character in s maps to exactly one character in t.
2. Every character in t is mapped to by exactly one character in s (no two different characters in s can map to the same character in t).

Fixed Code #

We need to track both directions of the mapping to enforce these rules. Here's a corrected version using hash maps:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false; // Early exit if lengths don't match
        
        unordered_map<char, char> s_to_t;
        unordered_map<char, char> t_to_s;
        
        for (int i = 0; i < s.size(); ++i) {
            char s_char = s[i];
            char t_char = t[i];
            
            // Check if s_char already has a conflicting mapping
            if (s_to_t.find(s_char) != s_to_t.end()) {
                if (s_to_t[s_char] != t_char) return false;
            } 
            // Check if t_char is already mapped by another s_char
            else if (t_to_s.find(t_char) != t_to_s.end()) {
                return false;
            } 
            // If no conflicts, set the bidirectional mapping
            else {
                s_to_t[s_char] = t_char;
                t_to_s[t_char] = s_char;
            }
        }
        return true;
    }
};

Optimized Version (Using Arrays) #

If you're working with ASCII characters, you can use arrays instead of hash maps for faster performance:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        
        char s_map[256] = {0}; // Tracks s -> t mappings
        char t_map[256] = {0}; // Tracks t -> s mappings
        
        for (int i = 0; i < s.size(); ++i) {
            char sc = s[i];
            char tc = t[i];
            
            if (s_map[sc] == 0 && t_map[tc] == 0) {
                s_map[sc] = tc;
                t_map[tc] = sc;
            } else if (s_map[sc] != tc || t_map[tc] != sc) {
                return false;
            }
        }
        return true;
    }
};

This code enforces the strict bidirectional mapping required for isomorphic strings, so it'll handle all test cases correctly.

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