Description

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

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

Solution

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> map, map_reversed;
        
        for (int i = 0; i < s.size(); ++i) {
            char& key = s[i];
            char& val = t[i];
            
            if (map.count(key) && map[key] != val) {
                return false;
            }
            map.insert({key, val});
        }
        
        for (auto pair : map) {
            const char key = pair.first;
            char& val = pair.second;
            
            if (map_reversed.count(val) && map_reversed[val] != key) {
                return false;
            }
            map_reversed.insert({val, key});
        }
        return true;
    }
};

Explanation

Pseudocode

procedure isIsomorphic(S, T)
	define M, N

    for i:=0 to size of S do
        K <- S[i]
        V <- T[i]
        if K exists in M and M[K] != V then
            return false
        else do
            M[K] <- V
        end if
    end for
             
    for each pair in M do
        K <- key of pair
        V <- value of pair
        if V exists in N and N[V] != K then 
            return false
        else do 
       		insert pair into N in reverse order
        end if
    end for
        
    return true
end procedure

Handling Exceptions

There are two cases that are not allowed in isomorphic strings.
1. When two same characters map to the different characters.
2. When two different characters map to the same character.

Reference

https://leetcode.com/problems/isomorphic-strings/