Problème : chaînes isomorphes

Étant données deux chaînes s et t, déterminer si elles sont isomorphes.

Deux chaînes sont dites isomorphes si on peut remplacer chaque caractère de s par un autre pour obtenir t. Toutes les occurrences d’un même caractère doivent être remplacées par le même caractère, tout en conservant l’ordre. Aucun caractère ne peut être mappé sur deux caractères différents, mais un caractère peut se mapper sur lui‑même.

Exemples :

• "egg" et "add" → vrai
• "foo" et "bar" → faux
• "paper" et "title" → vrai

On suppose que les deux chaînes ont la même longueur.

Approche avec deux tableaux de correspondance

L’idée est de maintenir deux tableaux de taille 256 (un pour chaque caractère possible) afin de vérifier la bijection entre les caractères de s et ceux de t.

#include <string>
#include <cstring>

class Solution {
public:
    bool isIsomorphic(std::string s, std::string t) {
        if (s.length() != t.length()) return false;

        char mappingS[256] = {0};
        char mappingT[256] = {0};

        for (int i = 0; i < s.length(); ++i) {
            unsigned char cs = static_cast<unsigned char>(s[i]);
            unsigned char ct = static_cast<unsigned char>(t[i]);

            if (mappingS[cs] != 0 && mappingS[cs] != ct)
                return false;
            if (mappingT[ct] != 0 && mappingT[ct] != cs)
                return false;

            mappingS[cs] = ct;
            mappingT[ct] = cs;
        }
        return true;
    }
};

Approche avec une seule map et double parcours

On peut aussi utiliesr un dictionnaire pour enregistrer la correspondance de s vers t, puis inversement, afin de garantir la bijection.

#include <string>
#include <map>

class Solution {
public:
    bool isIsomorphic(std::string s, std::string t) {
        if (s.length() != t.length()) return false;

        std::map<char, char> forward;
        for (int i = 0; i < s.length(); ++i) {
            if (forward.find(s[i]) == forward.end())
                forward[s[i]] = t[i];
            else if (forward[s[i]] != t[i])
                return false;
        }

        std::map<char, char> backward;
        for (int i = 0; i < t.length(); ++i) {
            if (backward.find(t[i]) == backward.end())
                backward[t[i]] = s[i];
            else if (backward[t[i]] != s[i])
                return false;
        }
        return true;
    }
};

Approche par transformation en motif générique

On peut transformer chaque chaîne en un motif où chaque nouveau caractère est remplacé par un symbole incrémental (par exemple '0', '1', ...). Si les deux motifs sont identiques, les chaînes sont isomorphes.

#include <string>
#include <cstring>

class Solution {
private:
    std::string toPattern(const std::string& str) {
        std::string result = str;
        char map[256] = {0};
        char next = '0';
        for (int i = 0; i < str.length(); ++i) {
            unsigned char c = static_cast<unsigned char>(str[i]);
            if (map[c] == 0) {
                map[c] = next++;
            }
            result[i] = map[c];
        }
        return result;
    }

public:
    bool isIsomorphic(std::string s, std::string t) {
        if (s.length() != t.length()) return false;
        return toPattern(s) == toPattern(t);
    }
};

Ces trois implémentations respectent la contrainte de bijection entre les caractères des deux chaînes et parcourent chaque chaîne en temps linéaire O(n), avec une mémoire constante (tableaux de taille 256).