LeetCode 205. Isomorphic Strings

Description

https://leetcode.com/problems/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 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 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

Explanation

First, check if s and t have the same number of unique characters. Second, check if the orders of characters from two strings match. Third, check if each mapping character has the same number of occurrences.

Python Solution

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        
        counter1 = collections.Counter(s)
        counter2 = collections.Counter(t)
                
        if len(counter1) != len(counter2):
            return False
        
        mapping = {}
        
        for c1, c2 in zip(s, t):                        
            if c1 not in mapping:
                mapping[c1] = c2
            else:
                if c2 != mapping[c1]:
                    return False
                    
            if counter1[c1] != counter2[c2]:
                return False

        return True
        

• Time Complexity: ~N
• Space Complexity: ~N