205. Isomorphic Strings

Isomorphic strings are two strings where characters at the same index in both strings can be replaced to make the strings equal. In other words, if we can replace all occurrences of one character in the first string with another character and obtain the second string, and vice versa, then the strings are isomorphic.

In this blog, we’ll explore the concept of isomorphic strings and delve into a Java solution to determine whether two given strings are isomorphic.

Understanding Isomorphic Strings

To determine if two strings, s and t, are isomorphic, we need to establish a one-to-one mapping between characters in s and t. This means that each character in s should map to a unique character in t, and vice versa. Additionally, the length of both strings should be equal.

For example:

• “egg” and “add” are isomorphic because we can map ‘e’ to ‘a’ and ‘g’ to ‘d’.
• “foo” and “bar” are not isomorphic because there is no one-to-one mapping between characters.

Java Solution

Here’s the Java solution to determine whether two given strings, s and t, are isomorphic:

``````class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> mapS2T = new HashMap<>();
HashMap<Character, Character> mapT2S = new HashMap<>();

for (int i = 0; i < s.length(); i++) {
char charS = s.charAt(i);
char charT = t.charAt(i);

// Check if there's a mapping for charS in mapS2T and if it maps to the same character in t
if (mapS2T.containsKey(charS)) {
if (mapS2T.get(charS) != charT) {
return false;
}
} else { // If no mapping exists, check if charT is already mapped to some other character in mapT2S
if (mapT2S.containsKey(charT)) {
return false;
}

// Create new mapping since it's valid
mapS2T.put(charS, charT);
mapT2S.put(charT, charS);
}
}

return true;
}
}
``````

https://leetcode.com/problems/isomorphic-strings/description/?envType=daily-question&envId=2024-04-02

Explanation of the Solution

• We use two HashMaps, `mapS2T` and `mapT2S`, to store mappings from characters in s to characters in t, and vice versa, respectively.
• We iterate through each character in s and t simultaneously.
• For each character pair, we check if there’s an existing mapping in either map. If there is, we verify that it’s consistent with the current character pair. If not, we create a new mapping.
• If at any point we encounter an inconsistency, we return false. Otherwise, we return true, indicating that the strings are isomorphic.

In conclusion, understanding isomorphic strings and implementing a solution to determine their equality is essential in various algorithmic problems. The provided Java solution offers a concise and efficient approach to solve this problem.