Isomorphic Strings - Leetcode Solution

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.

1