HomeLeetcode205. Isomorphic Strings - Leetcode Solutions
Leetcode

205. Isomorphic Strings – Leetcode Solutions

Declan Clarke

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

Solution in Python

Python
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Edge case: if the lengths of s and t are not the same, they cannot be isomorphic
        if len(s) != len(t):
            return False
        
        # Two dictionaries to store the mappings from s to t and t to s
        map_s_to_t = {}
        map_t_to_s = {}
        
        # Iterate over the characters in both strings simultaneously
        for char_s, char_t in zip(s, t):
            # Check if there is a previous mapping from char_s to char_t
            if char_s in map_s_to_t:
                # If the current mapping does not match the existing one, return False
                if map_s_to_t[char_s] != char_t:
                    return False
            else:
                # Establish a new mapping from char_s to char_t
                map_s_to_t[char_s] = char_t
            
            # Similarly, check if there is a previous mapping from char_t to char_s
            if char_t in map_t_to_s:
                # If the current mapping does not match the existing one, return False
                if map_t_to_s[char_t] != char_s:
                    return False
            else:
                # Establish a new mapping from char_t to char_s
                map_t_to_s[char_t] = char_s
        
        # If all characters are consistently mapped, the strings are isomorphic
        return True

Explanation:

  1. Edge Case Handling:
    • The function first checks if the lengths of s and t are the same. If they are not, the strings cannot be isomorphic, so it returns False.
  2. Mapping Dictionaries:
    • Two dictionaries (map_s_to_t and map_t_to_s) are used to keep track of the mappings between the characters in s and t.
    • map_s_to_t maps characters from s to t, and map_t_to_s maps characters from t to s.
  3. Iterating Through Characters:
    • The function iterates through the characters of s and t simultaneously using the zip function.
    • For each pair of characters, it checks if a mapping already exists in the dictionaries:
      • If a mapping exists but does not match the current character, it returns False.
      • If no mapping exists, it creates a new one.
  4. Final Check:
    • If all characters are consistently mapped between s and t, the function returns True, indicating that the strings are isomorphic.

Solution in Javascript

JavaScript
var isIsomorphic = function(s, t) {
    // Edge case: if the lengths of s and t are not the same, they cannot be isomorphic
    if (s.length !== t.length) {
        return false;
    }

    // Objects to store the mappings from s to t and t to s
    let mapSToT = {};
    let mapTToS = {};

    // Iterate over the characters in both strings simultaneously
    for (let i = 0; i < s.length; i++) {
        let charS = s[i];
        let charT = t[i];

        // Check if there is a previous mapping from charS to charT
        if (mapSToT[charS] !== undefined) {
            // If the current mapping does not match the existing one, return false
            if (mapSToT[charS] !== charT) {
                return false;
            }
        } else {
            // Establish a new mapping from charS to charT
            mapSToT[charS] = charT;
        }

        // Similarly, check if there is a previous mapping from charT to charS
        if (mapTToS[charT] !== undefined) {
            // If the current mapping does not match the existing one, return false
            if (mapTToS[charT] !== charS) {
                return false;
            }
        } else {
            // Establish a new mapping from charT to charS
            mapTToS[charT] = charS;
        }
    }

    // If all characters are consistently mapped, the strings are isomorphic
    return true;
};

Solution in Java

Java
import java.util.HashMap;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        // Edge case: if the lengths of s and t are not the same, they cannot be isomorphic
        if (s.length() != t.length()) {
            return false;
        }

        // HashMaps to store the mappings from s to t and t to s
        HashMap<Character, Character> mapSToT = new HashMap<>();
        HashMap<Character, Character> mapTToS = new HashMap<>();

        // Iterate over the characters in both strings simultaneously
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            // Check if there is a previous mapping from charS to charT
            if (mapSToT.containsKey(charS)) {
                // If the current mapping does not match the existing one, return false
                if (mapSToT.get(charS) != charT) {
                    return false;
                }
            } else {
                // Establish a new mapping from charS to charT
                mapSToT.put(charS, charT);
            }

            // Similarly, check if there is a previous mapping from charT to charS
            if (mapTToS.containsKey(charT)) {
                // If the current mapping does not match the existing one, return false
                if (mapTToS.get(charT) != charS) {
                    return false;
                }
            } else {
                // Establish a new mapping from charT to charS
                mapTToS.put(charT, charS);
            }
        }

        // If all characters are consistently mapped, the strings are isomorphic
        return true;
    }
}

Solution in C#

C#
using System.Collections.Generic;

public class Solution {
    public bool IsIsomorphic(string s, string t) {
        // Edge case: if the lengths of s and t are not the same, they cannot be isomorphic
        if (s.Length != t.Length) {
            return false;
        }

        // Dictionaries to store the mappings from s to t and t to s
        Dictionary<char, char> mapSToT = new Dictionary<char, char>();
        Dictionary<char, char> mapTToS = new Dictionary<char, char>();

        // Iterate over the characters in both strings simultaneously
        for (int i = 0; i < s.Length; i++) {
            char charS = s[i];
            char charT = t[i];

            // Check if there is a previous mapping from charS to charT
            if (mapSToT.ContainsKey(charS)) {
                // If the current mapping does not match the existing one, return false
                if (mapSToT[charS] != charT) {
                    return false;
                }
            } else {
                // Establish a new mapping from charS to charT
                mapSToT[charS] = charT;
            }

            // Similarly, check if there is a previous mapping from charT to charS
            if (mapTToS.ContainsKey(charT)) {
                // If the current mapping does not match the existing one, return false
                if (mapTToS[charT] != charS) {
                    return false;
                }
            } else {
                // Establish a new mapping from charT to charS
                mapTToS[charT] = charS;
            }
        }

        // If all characters are consistently mapped, the strings are isomorphic
        return true;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com