# Solution For Isomorphic Strings

Problem Statement:

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:
Input: s = “egg”, t = “add”
Output: true

Example 2:
Input: s = “foo”, t = “bar”
Output: false

Example 3:
Input: s = “paper”, t = “title”
Output: true

Approach:

In this problem, we need to check if the characters in string s can be replaced to get string t. For a character in s to be replaced by a unique character in t, we need to keep track of all the characters that we have already replaced in s and their corresponding characters in t. Thus, we need to create a mapping of characters in s to characters in t.

We can create a mapping using a hash map or an array. For each character in s, we check if it already exists in the mapping. If it does, we check if its corresponding character in t matches the current character in t. If not, we return false as we cannot replace the character in s with two different characters in t. If the current character in s is not in the mapping, we add it to the mapping with its corresponding character in t. We do the same for string t by creating a second mapping.

Finally, we return true if we reach the end of both strings without any mismatches.

Algorithm:

1. Initialize two hash maps `s_map` and `t_map` to store mappings of characters in s to t and characters in t to s respectively.
2. For i ranging from 0 to length of s,
a. If s[i] is not in `s_map` and t[i] is not in `t_map`, add mappings `s[i]:t[i]` and `t[i]:s[i]` to the two maps respectively.
b. If s[i] is in `s_map` and t[i] is not equal to `s_map[s[i]]`, return False as we cannot replace s[i] with two different characters in t.
c. Similarly, if t[i] is in `t_map` and s[i] is not equal to `t_map[t[i]]`, return False.
3. If we reach the end of both strings without mismatches, return True as the strings are isomorphic.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the strings s and t. We visit each character once in both strings and do constant time hashmap lookups and updates in each iteration.

Space Complexity:

The space complexity of this algorithm is O(k), where k is the number of unique characters in the two strings. In the worst case, k can be 26 (lowercase English alphabets), and thus the space complexity can be considered O(1).

Code:

Here’s the Python3 implementation of the above algorithm:

class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_map, t_map = {}, {}
for i in range(len(s)):
if s[i] not in s_map and t[i] not in t_map:
s_map[s[i]] = t[i] t_map[t[i]] = s[i] elif s[i] in s_map and t[i] != s_map[s[i]]:
return False
elif t[i] in t_map and s[i] != t_map[t[i]]:
return False
return True

We can test the solution on the given examples to check if the output matches the expected output:

s = “egg”
print(Solution().isIsomorphic(s, t)) # True

s = “foo”
t = “bar”
print(Solution().isIsomorphic(s, t)) # False

s = “paper”
t = “title”
print(Solution().isIsomorphic(s, t)) # True

Thus, we have successfully solved the Isomorphic Strings problem on LeetCode.

## Step by Step Implementation For Isomorphic Strings

```public boolean isIsomorphic(String s, String t) {
if (s == null || t == null) return false;
if (s.length() != t.length()) return false;

HashMap map = new HashMap<>();

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

if (map.containsKey(c1)) {
if (map.get(c1) != c2) {
return false;
}
} else {
map.put(c1, c2);
}
}
return true;
}```
```def isIsomorphic(s, t):
return len(set(zip(s, t))) == len(set(s)) == len(set(t))```
```var isIsomorphic = function(s, t) {
//Create a map to store the characters of string s
var map = {};
//Create a set to store the mapped characters of string t
var set = new Set();

//Loop through each character in string s
for(var i = 0; i < s.length; i++){
//If the current character is not in the map
if(!(s[i] in map)){
//Add the current character to the map with the corresponding character from string t
map[s[i]] = t[i];
//Add the mapped character to the set
}
//If the current character is in the map
else{
//If the mapped character in string t does not match the character in the map, return false
if(t[i] !== map[s[i]]){
return false;
}
}
}
//If the loop completes, return true
return true;
};```
```class Solution {
public:
bool isIsomorphic(string s, string t) {
if(s.length() != t.length())
return false;

// key is the character in s, value is the corresponding character in t
unordered_map myMap;

for(int i = 0; i < s.length(); i++){
char c1 = s[i];
char c2 = t[i];

// if c1 has not been mapped to anything yet
if(myMap.find(c1) == myMap.end()){
// if c2 has already been mapped to something, then we have a conflict
if(myMap.find(c2) != myMap.end())
return false;
// otherwise, map c1 to c2
else
myMap[c1] = c2;
}
// if c1 has been mapped to something
else{
// if it doesn't map to c2, then we have a conflict
if(myMap[c1] != c2)
return false;
}
}
return true;
}
};```
`public bool IsIsomorphic(string s, string t) { // If the two strings are of different length, they cannot be isomorphic if (s.Length != t.Length) return false; // Create two dictionaries, one for each string, to store the mapping of // characters to indices Dictionary dict1 = new Dictionary(); Dictionary dict2 = new Dictionary(); // Loop through each character in the first string for (int i = 0; i < s.Length; i++) { // If the character doesn't exist in the first dictionary, add it if (!dict1.ContainsKey(s[i])) dict1.Add(s[i], i); // If the character doesn't exist in the second dictionary, add it if (!dict2.ContainsKey(t[i])) dict2.Add(t[i], i); // If the indices of the characters in the two dictionaries are not equal, // the strings are not isomorphic if (dict1[s[i]] != dict2[t[i]]) return false; } // If we've made it this far, the strings are isomorphic return true; }`

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]