Isomorphic Strings

Q: Pourquoi avez-vous besoin de deux tables de hachage pour des chaînes isomorphes ?

Une correspondance de s vers t détecte un caractère de s renommé de deux façons. Elle ne peut pas détecter deux caractères de s renommés en un même caractère, comme dans ab et aa . La correspondance de t vers s détecte ce cas.

Q: Un isomorphisme est-il symétrique ?

Oui. Un renommage bijectif peut être annulé : si s est renommé en t , inverser chaque nom transforme t de nouveau en s . isIsomorphic(s, t) et isIsomorphic(t, s) donnent toujours le même résultat.

FacileHachage

+10

Deux chaînes sont isomorphes lorsque l’on peut renommer les caractères de la première pour obtenir la seconde. Chaque occurrence d’un caractère reçoit le même nouveau nom, deux caractères différents ne reçoivent jamais le même nom, et un caractère peut garder le sien. Pour deux chaînes s et t de même longueur, renvoie true lorsqu’elles sont isomorphes et false lorsqu’elles ne le sont pas.

Fonction

isIsomorphic(s: string, t: string) → boolean

sstring: la chaîne à renommer, des lettres et des chiffres
tstring: la chaîne à atteindre, de la même longueur que s
Renvoieboolean: vrai si un renommage bijectif des caractères de s donne t

Contraintes

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s et t contiennent uniquement des lettres anglaises et des chiffres. Les majuscules et les minuscules sont des caractères différents.

Exemples

Entrée: s = "noon"t = "deed"
Sortie: true
Explication: Renommez n en d et o en e. Chaque position est cohérente avec ce renommage, et les deux lettres reçoivent des noms différents.

Entrée: s = "moon"t = "deed"
Sortie: false
Explication: De gauche à droite, m devient d et o devient e, puis n devrait également devenir d. Deux lettres différentes ne peuvent pas partager un nom, donc la réponse est false.

Entrée: s = "r2d2"t = "c3p3"
Sortie: true
Explication: r devient c, 2 devient 3 et d devient p. Les chiffres sont aussi des caractères, et les deux 2 deviennent 3.

Pour aller plus loin

Étant donné une liste de mots, peux-tu regrouper ceux qui sont isomorphes entre eux sans comparer chaque paire de mots ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un renommage doit fonctionner dans les deux sens : chaque caractère de s devient un caractère de t, et chaque caractère de t provient d’un caractère de s. Deux tables de correspondance, une pour chaque sens, vérifient les deux en un seul passage.

Comparez chaque paire de positions

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Un renommage conserve l’égalité des caractères et la différence entre les caractères. Ainsi, pour chaque paire de positions i et j, s[i] == s[j] doit donner la même réponse que t[i] == t[j]. Cela suffit également : si chaque paire concorde, le renommage de chaque caractère de s en celui de t aux mêmes positions est bien défini et n’attribue jamais le même nom à deux caractères. Dans moon et deed, les positions 0 et 3 contiennent des lettres différentes dans s, mais deux fois d dans t ; la réponse est donc false.

Il y a environ n²/2 paires : 2 × 10^8 comparaisons pour n = 2 × 10^4 lorsqu’aucune paire n’interrompt la boucle prématurément.

Algorithme

Parcours chaque indice i, et pour chacun, chaque indice ultérieur j.
Détermine si s[i] est égal à s[j], et si t[i] est égal à t[j].
Si les deux réponses diffèrent, retourne false.
Après la dernière paire, retourne true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Deux maps, une par direction

Intuition

Construisez le renommage au fur et à mesure de la lecture. sToT indique ce que devient chaque caractère de s, et tToS indique de quel caractère provient chaque caractère de t. À la position i, avec a = s[i] et b = t[i], soit les deux sont nouveaux et vous les associez, soit ils doivent déjà pointer l’un vers l’autre.

Une seule table ne suffit pas. Avec seulement sToT, moon et deed sont acceptés, car aucune lettre de s n’est renommée de deux façons différentes. Le problème est que m et n deviennent tous deux d, et à la position 3, tToS indique déjà que d provient de m.

Chaque position nécessite quelques opérations sur les tables, donc le temps d’exécution est de O(n). Le code de chaque caractère est inférieur à 128, donc chaque table peut être un tableau de 128 entrées : espace O(1). Les versions R et Swift copient d’abord les chaînes dans des tableaux de codes, ce qui prend O(n).

Algorithme

Créez deux tables vides, sToT et tToS.
Pour chaque indice i, soit a = s[i] et b = t[i].
Si a ne figure pas dans sToT et que b ne figure pas dans tToS, associez a à b et b à a.
Sinon, si sToT[a] n'est pas b ou si tToS[b] n'est pas a, renvoyez false.
Après le dernier indice, renvoyez true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Pièges et cas limites

Ne conserver qu’une seule correspondance de s vers t. Cela accepte moon et deed, ainsi que ab et aa.
Comparer le nombre d’occurrences de chaque caractère. abcabc et xyzxzy utilisent tous deux trois caractères apparaissant chacun deux fois, pourtant le deuxième b correspond à z, alors que le premier correspondait à y.
Considérer les majuscules et les minuscules comme identiques. aA contient deux caractères différents, il ne peut donc pas devenir bb.
Dimensionner les tableaux de correspondance pour les caractères de a à z uniquement. Les majuscules et les chiffres sortent de cette plage ; utilisez l’index du code de caractère complet avec 128 entrées.

Questions fréquentes4

Quelle est la complexité temporelle des chaînes isomorphes ?

La solution à deux maps lit chaque position une seule fois, donc son temps d’exécution est de O(n). Les maps contiennent au maximum une entrée par caractère possible, soit 62 lettres et chiffres ; l’espace supplémentaire est donc de O(1). Comparer chaque paire de positions prend O(n²).

Pourquoi avez-vous besoin de deux tables de hachage pour des chaînes isomorphes ?

Une correspondance de s vers t détecte un caractère de s renommé de deux façons. Elle ne peut pas détecter deux caractères de s renommés en un même caractère, comme dans ab et aa. La correspondance de t vers s détecte ce cas.

Un isomorphisme est-il symétrique ?

Oui. Un renommage bijectif peut être annulé : si s est renommé en t, inverser chaque nom transforme t de nouveau en s. isIsomorphic(s, t) et isIsomorphic(t, s) donnent toujours le même résultat.

Comment autrement pouvez-vous vérifier si deux chaînes sont isomorphes ?

Remplacez chaque caractère par la position où il apparaît pour la première fois et comparez les résultats. noon et deed deviennent tous deux 0 1 1 0, tandis que moon devient 0 1 1 3. Cette méthode prend également un temps O(n) et nécessite une mémoire de O(n) pour les deux motifs.

def isIsomorphic(s, t):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

s = "noon"
t = "deed"

Résultat attendu

true