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
Note:
You may assume both s and t have the same length.
The description was taken from https://leetcode.com/problems/isomorphic-strings/.
#Hashmap#O(N) Time, O(N) Space
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
def occurrence_count(s):
seen = {}
result = []
occurrence = 1
for char in s:
if char not in seen:
seen[char] = occurrence
occurrence += 1
result.append(seen[char])
return result
string_one = occurrence_count(s)
string_two = occurrence_count(t)
return string_one == string_two#Hashset#O(N) Time, O(N) Spaceclass Solution: def isIsomorphic(self, s: str, t: str) -> bool: return len(set(zip(s, t))) == len(set(s)) == len(set(t))If the characters of a string could be swapped out successfully, that means the occurrence of each new character moving from left to right would have to be the same.
Knowing this, we can utilize a hashmap to store characters that we have seen before. If we encounter a new character that we haven't seen, we will update an occurrence counter.
However, that would just verify that the frequency of characters would be the same and would be able to be swapped out but the ordering would not yet be validated. To account for this, at the end of each iteration while we traverse the strings, we will append the order that the current character first occurred into a list. That way, once we have finished traversing both strings, we will have two ordered lists to compare for both strings, if the lists are the same then the strings are isomorphic.
Let's start by creating an occurence_count helper function that we will pass both strings into.
def occurrence_count(s):
We'll need a dictionary to keep track of characters we have seen before, and a result list that will give us the order of each occurrence count, as well as the initial new character occurrence count itself.
seen = {}
result = []
occurrence = 1
For each character in the given string, if the character has not been seen before, then we will place it in the seen dictionary and increment our new character occurrence counter.
if char not in seen:
seen[char] = occurrence
occurrence += 1
Whether we marked the new occurrence in the dictionary, or if it was already there, we will output the occurrence count of the current character to the result.
result.append(seen[char])
Once we have traversed the entire string, we will return the result.
return result
Now that we have our helper function built, we will pass in both strings to get both ordered lists. Then, we will return if those orderings are the same.
For example, "paper" and "title" would result in [1, 2, 1, 3, 4] and [1, 2, 1, 3, 4].
string_one = occurrence_count(s)
string_two = occurrence_count(t)
return string_one == string_two
To solve this question, we can use HashSets to isolate the count of unique characters in each string. Afterward, we can check the mapping of the unique characters as well.
The solution above has a bunch of logic packed into one line so let's break it down.
We want to first check the mapping of the characters. We'll use this test case for example:
Input: s = "paper", t = "title"
In this portion of the solution, we check the mapping of unique characters.
len(set(zip(s, t)))
We can zip the two strings together. This will give us a zip object that pairs together the characters in both strings.
{('p', 't'), ('a', 'i'), ('p', 't'), ('e', 'l'), ('r', 'e')}
This object currently has five characters zipped together with some duplicate elements.
We can remove the duplicates to get a unique mapping by using a set. The pairings become:
{('a', 'i'), ('r', 'e'), ('e', 'l'), ('p', 't')}
Now we have a character mapping of four unique characters within each string:
p->t
a->i
e->l
r->e
We also need to make sure we have the same amount of unique characters in each string.
len(set(s)) == len(set(t))
If there are a different amount of unique characters within the two strings, then the unique characters from another string won't be able to be swapped between the two interchangeably.
Now that we have mapped the unique characters to each other and made sure the length of unique characters are the same in both strings, we will need to make sure that the mapping count is the same as the length of the unique characters in both strings.
return len(set(zip(s, t))) == len(set(s)) == len(set(t))
In "title" and "paper", there are four unique characters mapping to four unique characters, making the strings Isomorphic.