[Top Interview 150] 205. Isomorphic Strings

Solution)

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        dic = {}

        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]] = t[i]
            else:
                if dic[s[i]] != t[i]:
                    return False
        
        countDic = Counter(dic.values())
        
        for count in countDic.values():
            if count > 1:
                return False
        
        return True

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)

Explanation)

First, using a dictionary, set characters in s as key and set characters in t as its matching value.
Check if the same character in s has different matching characters in t.
 
Then, we'll check if two different characters in s map to the same character in t by making a Counter of original dictionary's values
 
If all the conditions are met, then we'll return True.

Initialization)

Since we'll be mapping characters of s to characters of t, we'll use a dictionary.
 

def isIsomorphic(self, s: str, t: str) -> bool:
        dic = {}

Iteration)

As we iterate s, we'll set characters of s as a key and characters of t as a a value.
 
However, if we find a character of s that already exists in a dictionary, we'll compare its value and the current character of t. If they do not match, that means s and t are not isomorphic, thus we'll return False.
 

def isIsomorphic(self, s: str, t: str) -> bool:
        dic = {}

        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]] = t[i]
            else:
                if dic[s[i]] != t[i]:
                    return False

Check Values)

After the iteration is done, we need to check whether there is a duplicate in the dictionary's values.
We do this so that we can ensure that no two characters map the same character.
 

Need to check a duplicate in the values

So we'll use Counter from collections.
Once we make a counter dictionary using Counter(), we'll check if there exists a duplicate.
 
countDic will have characters of t as its key and the frequencies of those characters as its value.
Since we only want to know the frequencies, we'll just check if countDic has a value that is more than 1.
 

def isIsomorphic(self, s: str, t: str) -> bool:
        dic = {}

        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]] = t[i]
            else:
                if dic[s[i]] != t[i]:
                    return False
        
        countDic = Counter(dic.values())
        
        for count in countDic.values():
            if count > 1:
                return False
        
        return True

 
 
Checking the frequencies was the tricky part for me. Once I figured out Counter, the problem was solved with less  trouble.