Isomorphic String

Problem Statement:

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.

Examples:

Input: s = "egg", t = "add"
Output: true
Input: s = "foo", t = "bar"
Output: false
Input: s = "paper", t = "title"
Output: true

Solution: By now, you must have understood the question better, Although it is falls in easy category on LC, but it is not that intuitive. Here, we will discuss two approaches:

Approach 1(Intuitive):

Step 1: Encode the characters of String ‘s’ by providing a unique key to each character.

Step 2: Follow Step 1 for String T.(Note: The encoding mechanism is same for both String S and T as it would be easier for us to compare)

Step 3: Encoding Mechansim:

a. For each character in given String, if you are seeing that character for the first time.

b. Add the encoding value to the list for each character

c. Return the Encoding List

Step 4: Follow the Encoding Mechanism for both String S and T..

Step 5: Compare the encoding List of S and T.

Time Complexity: O(N)
Space Complexity: O(N)

Below is the code snippet:

Approach 2:

Step 1: Map each character of String S with each character of String T by starting with index=0.

Step 2: The moment, the mapped character of any of the characters of both S and T differs, return False

Step 3: If mapping happens perfectly then Step 2 will lever occur and hence, after the loop return True

Time Complexity: O(N)
Space Complexity: O(N)

Below is the code snippet:

Do follow and hit clap if you like this Article.

Happy Coding!