:orphan:

Isomorphic Strings
==================

.. highlight:: none

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

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:**

.. container:: example-block

   **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:**

.. container:: example-block

   **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:**

.. container:: example-block

   **Input:** s = "paper", t = "title"

   **Output:** true

 

**Constraints:**

- ``1 <= s.length <= 5 * 10``\ :sup:```4```
- ``t.length == s.length``
- ``s`` and ``t`` consist of any valid ascii character.

.. highlight:: python

Pattern
-------
Hash Table, String

Solution
--------
Observe that if two strings are isomorphic, then the first character in ``s``
must map to the first character in ``t``. Similarly, for the second character
to the last character. If the 2 strings are isomorphic, this is a one-to-one
map. We can use a dictionary to store the one-to-one map from ``s`` to ``t``.
Iterate through the characters in ``s`` and ``t`` at the same time. If the
``s`` character is not in the dictionary, then add it to the dictionary and to
the range set. Check injectivity, that the ``t`` character is not in the range
set. If the character in ``s`` is in the dictionary, then check if it maps to
the character in ``t``.

Code
----

.. literalinclude:: ../problems/easy/isomorphic-strings/isomorphic_strings__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from isomorphic_strings__approach_1 import isIsomorphic
>>> isIsomorphic('egg', 'add')
True
>>> isIsomorphic('foo', 'bar')
False
>>> isIsomorphic('paper', 'title')
True

Complexity
----------
| :math:`n` is the length of the shortest string
| Time: :math:`O(n)` — single pass through the strings
| Auxiliary Space: :math:`O(n)` — dictionary and range set store at most :math:`n` key-value pairs

.. autofunction:: isomorphic_strings__approach_1.isIsomorphic