Checking if two text blocks are isomorphic – Text blocks, Locales, Numbers & Math
11. Checking if two text blocks are isomorphic
Two text blocks are isomorphic if the resulting strings are isomorphic. 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 “qwwerr”. The one-to-one character mapping is as in figure 1.7:
Figure 1.7 – One-to-one character mapping between two strings
So, as you can see in figure 1.7, character ‘a’ of the first string can be replaced by character ‘q’ of the second string. Moreover, character ‘b’ of the first string can be replaced by character ‘w’ of the second string, character ‘c’ by character ‘e’, and character ‘d’ by character ‘r’. Obviously, the vice-versa is also true. In other words, these two strings are isomorphic.How about the strings “aab” and “que”? These two strings are not isomorphic because ‘a’ cannot be mapped to both ‘q’ and ‘u’.If we extrapolate this logic to text blocks then figure 1.8 is exactly what we need:
Figure 1.8 – Two isomorphic text blocks
Two text blocks are isomorphic if their string lines are isomorphic in a one-to-one fashion. Moreover, notice that essential white spaces and line terminators (LF) should be mapped as well, while incidental leading/trailing white spaces are ignored.The algorithm for ordinary string literals and text blocks is exactly the same and it relies on hashing – (more details about this topic are available in The Complete Coding Interview Guide in Java book, Example 6: Hash table) and consists of the following steps:
Check if the two text blocks (s1 and s2) have the same length. If their lengths differ then the text blocks are not isomorphic.
Create an empty map that will store mappings of the characters from s1 (as keys) to those of s2 (as values).
Pick up the first/next character from s1 (chs1) and s2 (chs2).
Check if chs1 is present as a key in the map.
If chs1 is present in the map as a key then it has to be mapped to a value from s2 that is equal to chs2, otherwise the text blocks are not isomorphic.
If chs1 is not present in the map as a key then the map shouldn’t contain chs2 as a value, otherwise the text blocks are not isomorphic.
If chs1 is not present in the map as a key and the map doesn’t contain chs2 as a value then put (chs1, chs2) in the map; chs1 as a key, and chs2 as a value
Repeat step 3 until the entire text block (s1) is processed.
If the entire text block (s1) was processed then the text blocks are isomorphic.
In code lines this O(n) algorithm can be expressed as follows:
public static boolean isIsomorphic(String s1, String s2) {
// step 1
if (s1 == null || s2 == null
|| s1.length() != s2.length()) {
return false;
}
// step 2
Map<Character, Character> map = new HashMap<>();
// step 3(8)
for (int i = 0; i < s1.length(); i++) {
char chs1 = s1.charAt(i);
char chs2 = s2.charAt(i);
// step 4
if (map.containsKey(chs1)) {
// step 5
if (map.get(chs1) != chs2) {
return false;
}
} else {
// step 6
if (map.containsValue(chs2)) {
return false;
}
// step 7
map.put(chs1, chs2);
}
}
// step 9
return true;
}
Done! You can practice this example in the bundled code. Well, this was the last problem covering text block topics. It is time to go further, and talk about strings concatenation.