Isomorphic Strings - LeetCode Daily Challenge

Problem Statement

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

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public boolean isIsomorphic(String s, String t) {

        Map<Character, Character> mappingStoT = new HashMap<>();
        Map<Character, Character> mappingTtoS = new HashMap<>();

        for(int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);

            if(!mappingStoT.containsKey(sChar)) {
                mappingStoT.put(sChar, tChar);
            }

            if(!mappingTtoS.containsKey(tChar)) {
                mappingTtoS.put(tChar, sChar);
            }

            if(mappingStoT.get(sChar) != tChar || mappingTtoS.get(tChar) != sChar) {
                return false;
            }
        }

        return true;
    }
}

C++ Code

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> mappingStoT;
        unordered_map<char, char> mappingTtoS;

        for(int i = 0; i < s.length(); i++) {
            char sChar = s[i];
            char tChar = t[i];

            if(!mappingStoT.count(sChar)) {
                mappingStoT[sChar] = tChar;
            }

            if(!mappingTtoS.count(tChar)) {
                mappingTtoS[tChar] = sChar;
            }

            if(mappingStoT[sChar] != tChar || mappingTtoS[tChar] != sChar) {
                return false;
            }
        }

        return true;
    }
};

Python Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mappingStoT = {}
        mappingTtoS = {}

        for i in range(len(s)):
            sChar = s[i]
            tChar = t[i]

            if sChar not in mappingStoT:
                mappingStoT[sChar] = tChar

            if tChar not in mappingTtoS:
                mappingTtoS[tChar] = sChar

            if mappingStoT[sChar] != tChar or mappingTtoS[tChar] != sChar:
                return False

        return True

Javascript Code

var isIsomorphic = function(s, t) {
    let mappingStoT = {};
    let mappingTtoS = {};

    for(let i = 0; i < s.length; i++) {
        let sChar = s[i];
        let tChar = t[i];

        if (!mappingStoT.hasOwnProperty(sChar)) {
            mappingStoT[sChar] = tChar;
        }

        if (!mappingTtoS.hasOwnProperty(tChar)) {
            mappingTtoS[tChar] = sChar;
        }

        if (mappingStoT[sChar] !== tChar || mappingTtoS[tChar] !== sChar) {
            return false;
        }
    }

    return true;
};

Go Code

func isIsomorphic(s string, t string) bool {
    mappingStoT := make(map[byte]byte)
    mappingTtoS := make(map[byte]byte)

    for i := 0; i < len(s); i++ {
        sChar := s[i]
        tChar := t[i]

        if _, ok := mappingStoT[sChar]; !ok {
            mappingStoT[sChar] = tChar
        }

        if _, ok := mappingTtoS[tChar]; !ok {
            mappingTtoS[tChar] = sChar
        }

        if mappingStoT[sChar] != tChar || mappingTtoS[tChar] != sChar {
            return false
        }
    }

    return true
}

Complexity Analysis

Time Complexity: O(N), we are iterating over the entire string once.
Space Complexity: O(1), we are storing 126 characters which is constant in the worst-case scenario in the map.