## Similar Problems

Similar Problems not available

# Isomorphic Strings - Leetcode Solution

LeetCode: Isomorphic Strings Leetcode Solution

Difficulty: Easy

Topics: string hash-table

## Isomorphic Strings

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 = “ddg”, t = “ssv”

Output: true

##### Example 2:

Input: s = “tree”, t = “eref”

Output: false

##### Example 3:

Input: s = “xyzz”, t = “abcc”

Output: true

**Note:**

- You may assume both s and t have the same length.

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:

- 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. - 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. - 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.

## Isomorphic Strings Solution Code

`1`