Isomorphic Strings.

Heyyyyy guys!

It's Tuesday Oct 2021, and it is day 25 of my coding diary.

Problem of the day - Isomorphic Strings

Tag - Easy

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

Problem statement is a bit complex to understand. I will do my bit to simplify it for you.

Two strings are given and we need to find out if we can generate the second string from first string by replacing a few or all words somehow.

This is called isomorphic.

As per the example, we can see -

e is replaced with a and g is replaced with d and we get the second string.

After some observation, the algorithm -

Maintain a hash map
Iterate over the first string
Check for the presence of the element, if no, set value with the respective element in second-string else check if the set value is same or not
One edge case is to check, many to one relationship.

We keep track of if a number is already mapped with some element or not.

Here is my code

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> mapping;
        map<char,int> visited;

        if(s.length() != t.length()) return false;

        for(int i=0;i<s.length();i++) {
            if(mapping[s[i]]) {
                if(mapping[s[i]] != t[i]) return false;
            } else {
                if(visited[t[i]]) return false;
            }
            mapping[s[i]] = t[i];
            visited[t[i]]++;
        }
        return true;
    }
};

Whenever I see, hashmap being used for characters. I get reminded of using an array. Let's optimize it further.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> mapping;
        int visited[129] = {0};

		// if not equal, return false
        if(s.length() != t.length()) return false;

        for(int i=0;i<s.length();i++) {
			// if already present
            if(mapping[s[i]]) {
				// if mapping is not correct
                if(mapping[s[i]] != t[i]) return false;
            } else {
				// if not present and visited
                if(visited[t[i]]) return false;
            }
            mapping[s[i]] = t[i];
            visited[t[i]]++;
        }
        return true;
    }
};

As, we know possible ASCII char is only 128. So, I have taken an array of fixed lengths.

Time and space complexity - O(n)

I feel, this problem should be in the medium section.

Please do let me know if you have some other approach to share.

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary