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();
        array<int, 128> last_s{}, last_t{};
        for (int i = 0; i < n; ++i) {
            if (last_s[s[i]] != last_t[t[i]]) {
                return false;
            }

            last_s[s[i]] = last_t[t[i]] = i + 1;
        }

        return true;
    }
};