205. Isomorphic Strings

Easy

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

Examples

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
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    s_to_t = {}
    t_to_s = {}
    
    for c1, c2 in zip(s, t):
        if c1 not in s_to_t and c2 not in t_to_s:
            s_to_t[c1] = c2
            t_to_s[c2] = c1
        elif s_to_t.get(c1) != c2 or t_to_s.get(c2) != c1:
            return False
    
    return True

Alternative Solution using character positions:


def isIsomorphic(s: str, t: str) -> bool:
    return len(set(zip(s, t))) == len(set(s)) == len(set(t))

Java Solution


class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        Map sToT = new HashMap<>();
        Map tToS = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            if (!sToT.containsKey(c1) && !tToS.containsKey(c2)) {
                sToT.put(c1, c2);
                tToS.put(c2, c1);
            } else if (sToT.getOrDefault(c1, '\0') != c2 || 
                      tToS.getOrDefault(c2, '\0') != c1) {
                return false;
            }
        }
        
        return true;
    }
}

C++ Solution


class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        unordered_map sToT;
        unordered_map tToS;
        
        for (int i = 0; i < s.length(); i++) {
            char c1 = s[i];
            char c2 = t[i];
            
            if (sToT.find(c1) == sToT.end() && tToS.find(c2) == tToS.end()) {
                sToT[c1] = c2;
                tToS[c2] = c1;
            } else if (sToT[c1] != c2 || tToS[c2] != c1) {
                return false;
            }
        }
        
        return true;
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    
    const sToT = new Map();
    const tToS = new Map();
    
    for (let i = 0; i < s.length; i++) {
        const c1 = s[i];
        const c2 = t[i];
        
        if (!sToT.has(c1) && !tToS.has(c2)) {
            sToT.set(c1, c2);
            tToS.set(c2, c1);
        } else if (sToT.get(c1) !== c2 || tToS.get(c2) !== c1) {
            return false;
        }
    }
    
    return true;
};

C# Solution


public class Solution {
    public bool IsIsomorphic(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        Dictionary sToT = new Dictionary();
        Dictionary tToS = new Dictionary();
        
        for (int i = 0; i < s.Length; i++) {
            char c1 = s[i];
            char c2 = t[i];
            
            if (!sToT.ContainsKey(c1) && !tToS.ContainsKey(c2)) {
                sToT[c1] = c2;
                tToS[c2] = c1;
            } else if (!sToT.ContainsKey(c1) || !tToS.ContainsKey(c2) ||
                      sToT[c1] != c2 || tToS[c2] != c1) {
                return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis

Solution Explanation

There are two main approaches to solve this problem:

Key Points

Common Pitfalls

Edge Cases