Checking if Two Strings are Isomorphic

In this article, we will learn to identify the isomorphic strings. We will discuss when the two strings are isomorphic and why this check is crucial in real-world applications.

1. What are Isomorphic Strings?

Two string literals are considered isomorphic if we can map every character of the first string to every character of the second string in a one-to-one fashion.

For example, consider that the first string is “abbcdd” and the second string is “qwwcrr“. The one-to-one character mapping can be shown as:

As we can see the character ‘a‘ of the string1 can be replaced by character ‘w‘ of the string2. Moreover, character ‘b‘ of the first string can be replaced by character ‘q‘ of the second string and character ‘d‘ by character ‘r‘. The vice-versa is also true. In other words, these two strings are isomorphic.

Let us take another example of strings “aab” and “que“. These two strings are not isomorphic because ‘a‘ cannot be mapped to both ‘q‘ and ‘u‘.

2. Why We Need to Check for Isomorphic Strings?

Most of the time, the recognition of isomorphic strings revolves around pattern matching for various purposes. For example:

• In data analysis, particularly in text processing, identifying isomorphic strings can help in pattern recognition, data normalization, and clustering of similar data.
• Isomorphic strings can be relevant in cryptographic algorithms where patterns and substitution ciphers play a role.
• In NLP, isomorphic strings can be used to identify similar linguistic patterns or to map one language to another.

3. The Algorithm to Check Isomorphic Strings

The algorithm to check if two strings are isomorphic involves comparing the characters of both strings and ensuring a one-to-one mapping between them.

The following is a pseudo algorithm:

• If String1 and String2 are ‘null‘ OR do not have the same length, return false.
• For each index ‘i‘ from ‘0‘ to the ‘length of String1 – 1‘:
  • Extract the character ‘char1‘ from String1 at index ‘i‘.
  • Extract the character ‘char2‘ from String2 at index ‘i‘.
• If the value at ‘Array1[char1]‘ is not equal to the value at ‘Array2[char2]‘, return false. This check ensures that a character in String1 always maps to the same character in String2.
• Update ‘Array1[char1]‘ and ‘Array2[char2]‘ to ‘i + 1‘ to record the latest index of mapping.
• If no mismatches were found, return ‘true‘, indicating the strings are isomorphic.

4. Java Example to Check Isomorphic Strings

Let us write a simple Java program to check for isomorphic Strings. The areIsomorphic() function takes two string arguments and determines whether two strings are isomorphic.

public class IsomorphicStrings {

  public boolean areIsomorphic(String s1, String s2) {

    if (s1 == null || s2 == null
        || s1.length() != s2.length()) {
      return false;
    }

    int[] arr1 = new int[256];
    int[] arr2 = new int[256];

    for (int i = 0; i < s1.length(); i++) {

      char c1 = s1.charAt(i);
      char c2 = s2.charAt(i);

      if (arr1[c1] != arr2[c2]) {
        return false;
      }

      arr1[c1] = i + 1;
      arr2[c2] = i + 1;
    }
    return true;
  }

  public static void main(String[] args) {

    IsomorphicStrings iso = new IsomorphicStrings();
    System.out.println(iso.areIsomorphic("abbcdd", "qwwcrr")); // true
    System.out.println(iso.areIsomorphic("aab", "que")); // false
  }
}

• In the very first step, we make null checks and compare the lengths of the two strings. If their lengths are not equal, they cannot be isomorphic because it will be impossible to have a one-to-one mapping between the characters of both strings.
• Then two integer arrays arr1 and arr2, each of size 256, are declared and initialized. The size 256 is chosen because there are 256 ASCII characters, and we are assuming the strings contain ASCII characters. These arrays are used to store the mapping of characters from each string.
• We iterate over the characters of the strings using a for-loop and check each character pair from s1 and s2. The ‘if (arr1[c1] != arr2[c2]) return false;’ statement checks if the current character c1 of s1 was previously mapped to a different character than the current character c2 of s2. If they don’t match, it means that either c1 has been paired with a different character before, or c2 has been paired with a different character, so the function returns false.
• If the characters pass the check, their mappings are updated in the respective arrays.
• If the loop completes without finding any mismatch in mappings, it means the strings are isomorphic, and the function returns true.

5. Performance

The time complexity of this algorithm is O(n), where n is the length of the string. This is because we need to traverse each character of the strings only once.

The space complexity is O(1), or constant space, as the space used for the mapping does not depend on the size of the input strings. This holds true especially when dealing with fixed-size character sets like ASCII.

So we can say that the algorithm is efficient with a linear time complexity, making it suitable for processing large volumes of data.

6. Conclusion

This tutorial discussed what are isomorphic strings, the algorithm to check if they truly are, and a Java program implementing the algorithm.

Finally, we looked into the performance of the algorithm.

Happy Learning !!

Source Code on Github