# 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:

- 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. - 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. - 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”

t = “add”

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; HashMapmap = 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 set.add(t[i]); } //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_mapmyMap; 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 Dictionarydict1 = 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; }