Leetcode 205 Isomorphic Strings

Problem description

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

• Explanation: The strings s and t can be made identical by:

  • Mapping ‘e’ to ‘a’.
  • Mapping ‘g’ to ‘d’.

Example 2:

• Input: s = “foo”, t = “bar”

• Output: false

• Explanation: The strings s and t can not be made identical as ‘o’ needs to be mapped to both ‘a’ and ‘r’.

Example 3:

• Input: s = “paper”, t = “title”

• Output: true

Constraints: Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

Problem Solving Process (Solution A)

We build a mapping dictionary from characters in s to characters in t.

While iterating through both strings:

1. If a character sc from s is already mapped

• Check if it maps to the same character tc in t.

  • If not, return False.

1. If sc is NOT mapped yet

• We need to also ensure that no other character already maps to tc.

• This guarantees a one-to-one mapping.

If we finish checking all characters without contradiction, return True.

Code Implementation

# Solution A
def isIsomorphic(s, t):
    ismor_map = {}
    
    #Edge case
    if not s or not t or len(s) != len(t):
        return False


    for sc, tc in zip(s,t):
        if sc in ismor_map:
            if ismor_map[sc] != tc: #Example: s='foo', t='bar'
                return False
            elif tc not in ismor_map.values(): #Example: s='bar', t='foo'
                return False
        char_map[sc] = tc
    return True

Complexity Analysis

• Time complexity: O(n). Since the for loop runs n times for s and t.

• Space complexity: O(n). In the solution, we created a new data structure to store the character mapping.

  • The maximum space complexity: The worst case is that we need to store all the character from a-z so in this case the space complexity is O(26)

Problem Solving Process (Solution B)

The idea of this solution is:

1. Convert string s to a set to keep only unique characters.

2. Convert string t to a set to keep only unique characters.

3. Zip the two strings into pairs and convert that into a set.

4. If all three sets have the same size, we assume the mapping is consistent.

Example | String | Unique chars | Count | | ———————- | ——————————————– | —– | | s = “paper” | {‘p’,’a’,’e’,’r’} | 4 | | t = “title” | {‘t’,’i’,’l’,’e’} | 4 | | pairs = set(zip(s, t)) | {(‘p’,’t’), (‘a’,’i’), (‘e’,’l’), (‘r’,’e’)} | 4 |

Code Implementation

def isIsomorphic(s, t):
    return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

Complexity Analysis

• Time Complexity: O(n): In this solution, we created three sets. Two are converted from string and one is character zip set. So the time complexity is O(3n) = O(n)

• Space Complexity: O(n): Since we used three extra data structure, the space complexity is O(3n) = O(n)

  • The maximum space complexity is O(26*3) = O(78)for the worse case.