Are the words isomorph?

Question

Are the words isomorphs? (Code-Golf)

This is my non-golfed, readable and linear (quasi-linear?) in complexity take of the above problem. For completeness I include the description:

Two words are isomorphs if they have the same pattern of letter repetitions. For example, both ESTATE and DUELED have pattern abcdca

ESTATE 
DUELED 
abcdca

because letters 1 and 6 are the same, letters 3 and 5 are the same, and nothing further. This also means the words are related by a substitution cipher, here with the matching E <-> D, S <-> U, T <-> E, A <-> L.

Write code that takes two words and checks whether they are isomorphs.

As always tests are included for easier understanding and modification.

def repetition_pattern(text):
    """
    Same letters get same numbers, small numbers are used first.
    Note: two-digits or higher numbers may be used if the the text is too long.

    >>> repetition_pattern('estate')
    '012320'
    >>> repetition_pattern('dueled')
    '012320'
    >>> repetition_pattern('longer example')
    '012345647891004'

    #    ^  ^      ^  4 stands for 'e' because 'e' is at 4-th position.
    #           ^^ Note the use of 10 after 9.
    """
    for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
        text = text.replace(unique_letter, str(index))
    return text

def are_isomorph(word_1, word_2):
    """
    Have the words (or string of arbitrary characters)
    the same the same `repetition_pattern` of letter repetitions?

    All the words with all different letters are trivially isomorphs to each other.

    >>> are_isomorph('estate', 'dueled')
    True
    >>> are_isomorph('estate'*10**4, 'dueled'*10**4)
    True
    >>> are_isomorph('foo', 'bar')
    False
    """
    return repetition_pattern(word_1) == repetition_pattern(word_2)

Answer 1

for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
    text = text.replace(unique_letter, str(index))
return text

You don't need to go through the set and sort, you can do:

for index, letter in enumerate(text):
    text = text.replace(letter, str(index))
return text

By the time it gets to the last "e" in "estate" and tries to replace it with "5", it will already have replaced it with "0" earlier on, and there won't be any "e"s left to replace. And it's not changing something while iterating over it, because strings are immutable.

More golf-ish and less readable is:

return ''.join(str(text.index(letter)) for letter in text)

Edit: Note for posterity: the above two methods have the same bug Gareth Rees identified, comparing 'decarbonist' and 'decarbonized', where one ends by adding number 10 and the other is a character longer and ends by adding numbers 1, 0 and they compare equally.End Edit

But @jonsharpe's comment asks if you need it to return a string; if you don't, then it could be a list of numbers, which is still very readable:

return [text.index(letter) for letter in text]

Minor things:

• are_isomorph is a mix of plural/singular naming. Maybe isomorphic(a, b)?
• Your code doesn't take uppercase/lowercase into account - should it?
• This approach will break without warning for an input with numbers in it, e.g.
  • repetition_pattern('abcdefghi1') is 0923456789. "b" changes to 1, then changes to 9 because the "1" at the end catches it, then it appears the two were originally the same character. (It might be outside the scope of the question and not a problem).

Answer 2

There is a Python feature that almost directly solves this problem, leading to a simple and fast solution.

from string import maketrans    # <-- Python 2, or
from str import maketrans       # <-- Python 3

def are_isomorph(string1, string2):
    return len(string1) == len(string2) and \
        string1.translate(maketrans(string1, string2)) == string2
        string2.translate(maketrans(string2, string1)) == string1

Answer 3

The code in the post does not work! Here's an example where it fails:

>>> are_isomorph('decarbonist', 'decarbonized')
True

The problem is that the eleventh distinct character gets represented by 10, but an occurrence of the second distinct character followed by the first distinct character is also represented by 10. You could avoid this confusion by representing the pattern as a list instead of a string:

def repetition_pattern(s):
    """Return the repetition pattern of the string s as a list of numbers,
    with same/different characters getting same/different numbers.

    """
    return list(map({c: i for i, c in enumerate(s)}.get, s))

or, if you don't care about algorithmic efficiency:

    return list(map(s.find, s))

but an alternative approach avoids generating a repetition pattern at all, but instead considers the pairs of corresponding characters in the two strings. If we have:

ESTATE
DUELED

then the pairs are E↔D, S↔U, T↔E and A↔L. The two strings are isomorphic if and only if these pairs constitute a bijection: that is, iff the first characters of the pairs are all distinct, and so are the second characters.

def isomorphic(s, t):
    """Return True if strings s and t are isomorphic: that is, if they
    have the same pattern of characters.

    >>> isomorphic('estate', 'dueled')
    True
    >>> isomorphic('estate'*10**4, 'dueled'*10**4)
    True
    >>> isomorphic('foo', 'bar')
    False

    """
    if len(s) != len(t):
        return False
    pairs = set(zip(s, t))
    return all(len(pairs) == len(set(c)) for c in zip(*pairs))

From a purely code golf point of view, however, the following seems hard to beat (especially in Python 2, where you can drop the list calls):

list(map(s.find, s)) == list(map(t.find, t))

Answer 4

text.replace() is \$\mathcal{O}(n)\$. Assuming we have a string of \$n\$ distinct characters your algorithm could devolve in to \$\mathcal{O}(n^2)\$. Of course your strings are likely never long enough for big O to matter.

In problems like this no matter what language you use it is often useful to build tables of characters.

def base_pattern(text):
    lst=[chr(i) for i in range(256)]

    for index, c in enumerate(text):
        lst[ord(c)] = index

    return [lst[ord(c)] for c in text]

def are_isomorph(word1, word2):
    return base_pattern(word1) == base_pattern(word2)