Checking whether two values are isomorphic in Swift

Question

Working through a book problem

Write a function that accepts two values and returns true if they are isomorphic. That is, each part of the value must map to precisely one other, but that might be itself. Tip: Strings A and B are considered isomorphic if you can replace all instances of each letter with another. For example, “tort” and “pump” are isomorphic, because you can replace both Ts with a P, the O with a U, and the R with an M. For integers you compare individual digits, so 1231 and 4564 are isomorphic numbers. For arrays you compare elements, so [1, 2, 1] and [4, 8, 4] are isomorphic.

The author recommends casting both values to a string, then storing a dictionary that maps each character to the other character.

func challenge57(first firstValue: Any, second secondValue: Any) -> Bool {
    let first = String(describing: firstValue)
    let second = String(describing: secondValue)
    
    guard first.count == second.count else { return false }
    
    var characterMap = [Character: Character]()
    let firstArray = Array(first)
    let secondArray = Array(second)
    
    for (index, character) in firstArray.enumerated() {
        let correspondingCharacter = secondArray[index]
        
        if let currentMapping = characterMap[character] {
            if currentMapping != correspondingCharacter {
                return false
            }
        } else {
            if characterMap.values.contains(correspondingCharacter) {
                return false
            }
            
            characterMap[character] = correspondingCharacter
        }
    }
    
    return true
}

However, contains() is a linear time operation making the overall approach quadratic, and I’m struggling to come up with an optimization. Curious to hear any guidance in the right direction.

Answer 1

Review of your code

It may be a matter of personal taste, but I see guard as a language feature to avoid the “if-let pyramid of doom” or to check against exceptional situations, but not as a general replacement for a negated condition. In other works, I would write

guard first.count == second.count else { return false }

as

if first.count != second.count { return false }

You convert the strings to arrays first, which is a good idea if subscripting by character position is needed later, as in

let correspondingCharacter = secondArray[index]

But the characters from both strings are accessed sequentially, so one can enumerate the characters in parallel and save the additional array storage:

for (character, correspondingCharacter) in zip(first, second) { ... }

The time-consuming

if characterMap.values.contains(correspondingCharacter)

can be avoided if we keep a set of all characters seen in the second string to far. Inserting a character into the set and checking if it was already present can be done with a single call.

You also should choose a more descriptive function name.

The code would then look like this:

func isomorphic(first firstValue: Any, second secondValue: Any) -> Bool {
    let first = String(describing: firstValue)
    let second = String(describing: secondValue)
    
    if first.count != second.count { return false }

    // Map from characters in the first string to characters in the second string:
    var characterMap = [Character: Character]()
    // All characters seen in the second string so far:
    var seen = Set<Character>()
    
    for (firstChar, secondChar) in zip(first, second) {
        if let currentMapping = characterMap[firstChar] {
            if currentMapping != secondChar { return false }
        } else {
            if !seen.insert(secondChar).inserted { return false }
            characterMap[firstChar] = secondChar
        }
    }
    
    return true
}

I also (usually) prefer to put the statements in blocks on separate lines, e.g.

if first.count != second.count {
    return false
}

but that again is a matter of personal taste. One advantage during debugging is that you can more easily set a breakpoint on that statement.

Review of the problem description and the API

It makes sense to say that two strings are isomorphic if there is a one-to-one correspondence between their characters. It makes also sense for arrays if their respective elements can be compared for equality, i.e. if the array elements conform to the Equatable protocol.

More generally, “each part of the value must map to precisely one other” makes sense for collections (whose elements are comparable).

But it makes no sense (in my opinion) to define this kind of “isomorphy” for arbitrary values. Of course you can convert any value to a string with String(describing:), but

• unless the values conform to CustomStringConvertible or a related protocol, the result is unspecified, and
• even if all values conform to CustomStringConvertible, the result may not be what one expects.

Examples demonstrating the second point:

• challenge57(first: [11, 2], second: [3, 44]) evaluates to false even though the arrays are isomorphic, because their string representations are not isomorphic.
• challenge57(first: [1, 2], second: ["1", "2"]) evaluates to false even though each element of the first array can be uniquely mapped to an element of the second array.
• challenge57(first: [], second: "12") evaluates to true because the string representation of the empty array happens to be isomorphic to "12".

Therefore a better API in my opinion would be

func isomorphic<C1, C2>(first: C1, second: C2) -> Bool 
where C1: Collection, C1.Element: Equatable, C2: Collection, C2.Element: Equatable

The downside is that we can no longer use dictionaries and sets for faster lookup. But we can implement a specialisation for the case of hashable elements, and that would be not much different from the code above:

func isomorphic<C1, C2>(first: C1, second: C2) -> Bool 
where C1: Collection, C1.Element: Hashable, C2: Collection, C2.Element: Hashable {
    if first.count != second.count {
        return false
    }
    
    // Map from elements in the first collection to characters in the second collection:
    var map = [C1.Element: C2.Element]()
    // All elements seen in the second collection so far:
    var seen = Set<C2.Element>()
    
    for (firstElement, secondElement) in zip(first, second) {
        if let currentMapping = map[firstElement] {
            if currentMapping != secondElement { return false }
        } else {
            if !seen.insert(secondElement).inserted { return false }
            map[firstElement] = secondElement
        }
    }

    return true
}

This works as expected for strings and arrays:

print(isomorphic(first: "tort", second: "pump")) // true
print(isomorphic(first: "1234", second: 1234)) // Syntax error
print(isomorphic(first: [11, 2], second: [3, 44])) // true
print(isomorphic(first: [1, 2], second: ["1", "2"])) // true

Defining two integers to be isomorphic if there is a one-to-one correspondence between their decimal digits seems a bit arbitrary to me. (Why decimal digits and not the binary digits? What about negative numbers?). But if that is wanted then I would separate it as a function overload:

func isomorphic(first: Int, second: Int) -> Bool {
    return isomorphic(first: String(first), second: String(second))
}

print(isomorphic(first: 1231, second: 4564)) // true