205. Isomorphic Strings Easy

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

Approach

Input: Two strings s and t

Output: Determine if they are isomorphic

This is a Hash Table problem.

Use two hash tables key_cache and val_cache to record key -> val and val -> key.

Let s be the key and t be the val.

Iterate through the string s:

• Check if the character corresponding to key in key_cache is consistent with the character in t.
• Check if the character corresponding to val in val_cache is consistent with the character in s.

Then record them in the corresponding hash tables.

If all checks are correct, return true.

Implementation

python

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # If lengths are different, they cannot be isomorphic
        if len(s) != len(t):
            return False

        # Two dictionaries: record the mapping relations of s->t and t->s respectively
        key_cache = {}  # Map characters in s to characters in t
        val_cache = {}  # Map characters in t to characters in s

        for i in range(len(s)):
            key = s[i]  # Character at the current position in s
            val = t[i]  # Character at the current position in t

            # If the character in s has appeared, but the mapped character is inconsistent with the current val, it's a conflict
            if key in key_cache and key_cache[key] != val:
                return False
            
            # If the character in t has appeared, but the mapped character is inconsistent with the current key, it's a conflict
            if val in val_cache and val_cache[val] != key:
                return False

            # Establish/Update bidirectional mapping relation
            key_cache[key] = val
            val_cache[val] = key
        
        # If traversal finishes without conflict, they are isomorphic strings
        return True

javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    if (s.length !== t.length) return false;

    const keyCache = {};
    const valCache = {};

    for (let i = 0; i < s.length; i++) {
        const key = s[i];
        const val = t[i];

        if (keyCache[key] && keyCache[key] !== val) return false;
        if (valCache[val] && valCache[val] !== key) return false;

        keyCache[key] = val;
        valCache[val] = key;
    }

    return true;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) space considering at most 256 ASCII characters

Links

205. Isomorphic Strings (English)205. 同构字符串 (Chinese)