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”
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;
    
    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
            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_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; }