205. Isomorphic Strings

1. 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.

2. Example

Example 1

Input: s = “egg”, t = “add”
Output: true
Explanation:
The strings s and t can be made identical by:

• Mapping ‘e’ to ‘a’.
• Mapping ‘g’ to ’d'.

Example 2

Input: s = “f11”, t = “b23”
Output: false
Explanation:
The strings s and t can not be made identical as ‘1’ needs to be mapped to both ‘2’ and ‘3’.

Example 3

Input: s = “paper”, t = “title”
Output: true

3. Constraints

• 1 <= s.length <= 5 * $10^4$
• t.length == s.length
• s and t consist of any valid ascii character.

4. Solutions

Hash Table

n = s.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    bool isIsomorphic(const string &s, const string &t) {
        const int n = s.size(), flag = numeric_limits<int>::max();
        array<int, 128> s_to_t, t_to_s;
        s_to_t.fill(flag);
        t_to_s.fill(flag);
        for (int i = 0; i < n; ++i) {
            if (s_to_t[s[i]] == flag && t_to_s[t[i]] == flag) {
                s_to_t[s[i]] = t[i];
                t_to_s[t[i]] = s[i];
            } else if (s_to_t[s[i]] != t[i] || t_to_s[t[i]] != s[i]) {
                return false;
            }
        }

        return true;
    }
};