Check if Two Strings Are Isomorphic in Scala

1. Introduction

In this tutorial, we’ll create a Scala function, checkIsomorphic, to check if two strings are isomorphic to each other.

Isomorphic strings have the property that when each character in the first string can be replaced by the corresponding character in the second, the result is the second string. Only when both strings are isomorphic to each other, then they are isomorphic. 

Examples of isomorphic strings are “egg” and “add” because we can replace “e” with “a” and “g” with “d” to get “add” and vice versa.

2. Solutions

In the following sections, we’ll look at a couple of checkIsomorphic Scala functions.

We’ll also examine a wrapper function checkIsomorphicBothWays, which returns true only if the input strings are both isomorphic to each other.

2.1. A Verbose Approach

Consider below a simple but verbose approach in Scala.

private def checkIsomorphic(str1: String, str2: String): Boolean =
  val z = str1.zip(str2)
  // for each distinct pair, count the number of occurrences of tup._1 char
  val distinctCounts = z.map(tup => {
    z.distinct.count(tupZ => tupZ._1 == tup._1)
  })
  distinctCounts.count(_ > 1) == 0

First, we zip str1 and str2 to get pairs of characters located at the same index. The next step counts the occurrences of each distinct pair in the sequence of character pairs “z” and returns a sequence of Integers corresponding to the number of times each pair occurs in “z”. We return true if all occurrences occur only once for each distinct pair.

2.2. A Less Verbose Approach

Consider the code below:

private def checkIsomorphic2(str1: String, str2: String): Boolean =
  val z = str1.zip(str2)
  val m = z.groupMap(_._1)(_._2)
  m.forall(_._2.distinct.length == 1)

In this approach, we zip the two strings to obtain a sequence of character pairs.

In the second step, we groupMap the sequence. For example, we group by “z” on the first character from the pair and map it to the concatenated sequence of the second character from the pair.

Finally, for all (Char -> String) entries in the map, if the String length is equal to 1, then str1 is isomorphic to str2.

3. checkIsomorphicBothWays Function

Following is the definition of the checkIsomorphicBothWays wrapper function:

def checkIsomorphicBothWays(str1: String, str2: String): Boolean =
  (str1.length == str2.length) && checkIsomorphic(
    str1,
    str2
  ) && checkIsomorphic(str2, str1)

The function checks the string lengths to be equal. Only then is it checked that str1 is isomorphic to str2 and vice versa. If all these conditions are true, the strings are isomorphic.

4. Conclusion

In this short article, we examined several ways to check for isomorphism between two strings.

The code examples for this article are available over on GitHub.