Isomorphic Strings

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 205. This is a Leet code problem named Isomorphic Strings. We will solve it using python and it is the best space and time-optimized solution.

Question of Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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

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

Constraints

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ASCII character.

Approach to solve Isomorphic Strings

To solve this problem we will run the for loop to iterate each element of both s and t strings. While traversing through them we check if it is repeated or visited. If it is repeated or visited then we check whether the pair of letters match the previous pair or not.

Algorithm

This method performs the following steps for a given input binary search tree:

Create a dictionary to store elements of s and t as key-value pairs respectively.
Create another dictionary to store elements of t and s as key-value pairs respectively.
Repeat steps 4 to till i=0 to 9 i is less than the length of s.
check if the current element of s is in s_visited dictionary then do step 5 otherwise go to step 6.
If the element in s[i] does not correspond to t[i] previously than return false.
check if the current element of t is in t_visited dictionary then do step 7 otherwise go to step 8.
If the element in t[i] does not correspond to s[i] previously than return false.
assign s_visited[s[i]] = t[i] and
t_visited[t[i]] = s[i]
end for
return True.

Python Code for Isomorphic Strings

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        
        #a dictionary to store elements of s and t as key-value pairs respectively
        s_visited = {}
        #a dictionary to store elements of t and s as key-value pairs respectively
        t_visited = {}
        
        #run for loop 
        for i in range(0 , len(s)):
            
            #check if current element of s is visited or not
            if(s[i] in s_visited ):
                #check element in s[i] corresponds to t[i] previously or not
                if( s_visited[s[i]] != t[i] ):
                    return False
            #check if current element of t is appeared before or not
            elif(t[i] in t_visited ):
                #check element in t[i] corresponds to s[i] previously or not
                if( t_visited[t[i]] != s[i] ):
                    return False
            else:
                s_visited[s[i]] = t[i]
                t_visited[t[i]] = s[i]
           
        return True