Problem

Determine whether there exists a one-to-one character mapping from one string s1 to another s2. For example, given s1 = abc and s2 = bcd, return true since we can map a to b, b to c, and c to d. Given s1 = foo and s2 = bar, return false since the o cannot map to two characters.

Understanding the Problem

What is asked to find ?

There are two strings. We need to find if there exists 1-1 mapping between the two strings.

Rephrasing the problem

One character from the first string can correspond to only one other character from the other string. And a to b relation is not equal to b to a relation. We need to find if strings have such one to one relations between their characters.

Diagram for clarification

Any Questions on the problem?

The given statement does not specify if these string pass the criteria: s1=”abc”, s2=”ccc”

In this example, each letter from s1 maps to “c”, this satisfies the mentioned condition of having each character from s1 maps to only one character “c” from s2. But the problem does not specify if it is allowed to have multiple characters from the first string mapped into a single character from the second string.

After looking at the Leetcode version of this statement, it states that:

No two characters may map to the same character, but a character may map to itself.

Devising a plan

Strategy that might work

Have you seen similar problem before?

It feels very similar to array searching problems like duplicate character check, where on has to go through the array and find which is the duplicate character or element. However, in this problem there is a slight change, we allow duplicate characters, but these characters must have the same mapping. If there are 2 ‘a’ in the string, both of them must resolve to same character in the other string.

Implementing the plan

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) { 
        return false 
    }
    m := make(map[string]string)
    for i:= 0; i < len(t); i++ {
        val, ok := m[string(s[i])]
        if ok {
            if string(val) != string(t[i]) {
                return false
            }
        } else {
            m[string(s[i])] = string(t[i])
        }
    }
    return true
}

This works well for about 40 of 47 use-cases.

This is because we missed a crucial detail that we had highlighted but not taken in consideration while planning the strategy to solve this. And that is:

No two characters may map to the same character, but a character may map to itself.

Revisiting the plan

Our plan was quite simplistic and did not account for the mentioned condition.

Diagram for clarification

Revision

Currently we only have a one way check to uniqueness of values, which means character from s1 (key) maps to an unique character in s2 (value). To resolve this issue, we can add another check for uniqueness of keys, which means each character from s2 (value) has a unique character in s1 (key).

Implementing the revision

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) { 
        return false 
    }
    key2value := make(map[string]string)
    value2key := make(map[string]string)
    for i:= 0; i < len(t); i++ {
        key, keyOk := value2key[string(t[i])]
        _, valueOk := key2value[string(s[i])]
        if keyOk {
            if valueOk {
                if string(s[i]) != key {
                    return false
                }
            } else {
                return false
            }
        } else {
            if valueOk {
                return false
            } else {
                key2value[string(s[i])] = string(t[i])
                value2key[string(t[i])] = string(s[i])
            }
            
        }
    }
    return true
}

When submitted this solution works for all available use-cases

IS THIS THE END?

The AI Outlook

Let’s see what does AI suggests us to improve this.

func isIsomorphic(s, t string) bool {
    if len(s) != len(t) {
        return false
    }

    key2value := make(map[byte]byte, len(s))
    value2key := make(map[byte]byte, len(s))

    for i := 0; i < len(s); i++ {
        k := s[i]
        v := t[i]

        mappedV, okV := key2value[k]
        mappedK, okK := value2key[v]

        if okV {
            if mappedV != v {
                return false
            }
        } else {
            if okK && mappedK != k {
                return false
            }
            key2value[k] = v
            value2key[v] = k
        }
    }
    return true
}

Not many changes on the algorithmic front other than:
– Converting string map to byte map
– Preallocating the map lengths
– Removing the string conversion overhead

Looking back

Looking at the process of devising a plan, we missed out on a major condition that should have been taken in for consideration.

This could have been improved if we had been less hasty to get to the easy solution; we would got this condition handled in the planning stage itself.