[LeetCode Road] Isomorphic Strings - Solution/C++

205. Isomorphic Strings

Question:

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:

Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 10⁴

t.length == s.length

s and t consist of any valid ascii character.

Source code

Version 1

Idea:
"Isomorphic" means that no more than one character of string can map to the same character. E.g., s1="apple" s2="paper", you can see two p alphabets of s1 map to a alphabet and p alphabet at s2, the result is false.

Hence, you need to record each character relationship (two strings) to unordered map container.
At 8-16 line, you should through all characters. If this character isn't exist in unmap_s and unmap_t, store a character of the other side. At 10 line, if a character isn't exist in unmap_s but it has already exist in numap_t, it means more than one character map to the same character, so return false.

At 13 line, if this character has already exist in unmap_s, you can get the value (=previous t[i]) then you find the value isn't equal to current t[i], return false.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        const int n = s.length();
        if(s == t) return true;
        unordered_map<int, int> unmap_s, unmap_t;
        
        for(int i = 0; i < n; i++){
            if(unmap_s.find(s[i]) == unmap_s.end()){
                if(unmap_t.find(t[i]) != unmap_t.end()) return false;
                unmap_s[s[i]] = t[i];
                unmap_t[t[i]] = s[i];
            }else if(unmap_s[s[i]] != t[i]){
                return false;
            }
        }
        return true;
    }
};

Version 2

Idea:
This strategy uses only one unordered map container. But I implemented a matchbyValue function to check value existence in container.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> record;
        unordered_map<char, char>::iterator it;
        
        const int n = s.length();
        for(int i = 0; i < n; i++){
            it = record.find(s[i]);
            if(it == record.end()){
                if(matchbyValue(record, t[i])){
                    return false;
                }else{
                    record.insert(pair<int,int>(s[i],t[i]));
                }
            }else{
                if(it->second == t[i]){
                    continue;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
private:
    bool matchbyValue(unordered_map<char, char> record, char target){
        auto it = record.begin();
        
        while(it != record.end()){
            if(it->second == target) return true;
            it++;
        }
        return false;
    }
};

Version 3

Idea:
It is an optimal approach that refered to online.
Initial two array to zero at first. At 10-11 line, store the position of character, i + 1 means the range of value is 1 to n, because inital value of array is zero.
So, if the values are not equal between map_s and map_t, return false. It represented characters are shown in different position. (characters are the same alphabet.)

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int map_s[128] = {0};
        int map_t[128] = {0};
        const int n = s.length();
        
        for(int i = 0; i < n; i++){
            if(map_s[s[i]] != map_t[t[i]]) return false;
            map_s[s[i]] = i + 1;
            map_t[t[i]] = i + 1;
        }
        return true;
    }
};