In simple terms, two strings are isomorphic if the characters in one string can be replaced to get the other string. Each character must map to exactly one character, and no two characters can map to the same character. For example:
- Isomorphic: “egg” and “add” -> “e” maps to “a”, and “g” maps to “d”
- Not Isomorophic: “foo” and “bar” -> “o” cannot map to two different characters (“a” and “r”).
The challenge is to determine whether two given strings are isomorphic efficiently.
Brute Force Approach
import java.util.HashMap;
import java.util.HashSet;
public class Solution {
public boolean isIsomorphic(String s, String t) {
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
if ((s.charAt(i) == s.charAt(j)) != (t.charAt(i) == t.charAt(j))) {
return false;
}
}
}
return true;
}
}• Compare every pair of indices in both strings to ensure that corresponding characters in s and t map consistently.
• If mismatched mappings are found, return false.
Optimized Approach
Algorithm: Using Two Arrays for Mapping
• Use two arrays (mapS and mapT) to keep track of mappings between characters of s and t.
• Each array has a size of 256 (for ASCII values) to store the last seen position of each character.
• If the last seen positions of a character in s and its corresponding character in t differ, the strings are not isomorphic.
public class Solution {
public boolean isIsomorphic(String s, String t) {
// Arrays to track character mappings
int[] mapS = new int[256];
int[] mapT = new int[256];
// Traverse both strings
for (int i = 0; i < s.length(); i++) {
char charS = s.charAt(i);
char charT = t.charAt(i);
// Check if mappings are inconsistent
if (mapS[charS] != mapT[charT]) {
return false;
}
// Update mapping positions
mapS[charS] = i + 1;
mapT[charT] = i + 1;
}
return true;
}
}Line-By-Line Explanation
Step 1: Declaring the Arrays
int[] mapS = new int[256];
int[] mapT = new int[256];• Creates two arrays, mapS and mapT, of size 256 to represent mappings for all possible ASCII characters.
• Each index in the arrays corresponds to a character’s ASCII value. For example, mapS[‘a’] stores data related to the character ‘a’.
• These arrays keep track of the last seen position of each character in s and t.
• The use of arrays ensures constant-time access for each character.
Step 2: Iterating Through the Strings
for (int i = 0; i < s.length(); i++) {
char charS = s.charAt(i);
char charT = t.charAt(i);• Processes the strings iteratively, which is simple and avoids recursion overhead.
• The use of indices ensures clarity and minimizes potential off-by-one errors.
Step 3: Checking for Mapping Inconsistencies
if (mapS[charS] != mapT[charT]) {
return false;
}- To ensure a one-to-one correspondence between characters in s and t. If the mapping for any character pair is inconsistent, the strings cannot be isomorphic.
Step 5: Updating the Mapping
mapS[charS] = i + 1;
mapT[charT] = i + 1;• To keep track of when each character was last seen in the strings.
• By ensuring that the mapping is updated on every character comparison, the algorithm ensures consistency throughout the strings.
Why This Code Works
The code works because it ensures that:
• Each character in s maps to exactly one character in t.
• Each character in t maps to exactly one character in s.
By leveraging arrays for constant-time mapping checks and updates, the code efficiently validates the one-to-one correspondence required for isomorphic strings.
