205. Isomorphic Strings

Intuition

The problem requires determining if two strings, s and t, are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t, with each character in s mapping to exactly one character in t and vice versa, preserving the order of characters.

Approach

1. Length Check: First, check if the lengths of s and t are different. If they are, return false as strings of different lengths cannot be isomorphic.
2. Mapping Creation: Use two dictionaries to create mappings from characters in s to characters in t and from characters in t to characters in s.
3. Iterate and Map: Iterate through each character pair (c1, c2) from s and t. - Check if there is an existing mapping for c1 in the s to t dictionary and for c2 in the t to s dictionary. - If there is a conflict in the mapping, return false. - Otherwise, create the mappings in both dictionaries.
4. Return True If all character pairs are processed without conflicts, return true.

This approach ensures that each character in s maps to exactly one character in t and vice versa, thereby determining if the strings are isomorphic.

Complexity

Time Complexity

• Iterating through the characters of s and t takes O(n) time, where n is the length of the strings.
• Overall time complexity is O(n).

Space Complexity

• The space complexity is O(1) since the dictionaries will hold at most 256 key-value pairs if we consider all possible ASCII characters. This can be considered constant space.

Code

C++

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

Python

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        mapST = {}
        mapTS = {}
        for c1, c2 in zip(s, t):
            if (c1 in mapST and mapST[c1] != c2) or (c2 in mapTS and mapTS[c2] != c1):
                return False
            mapST[c1] = c2
            mapTS[c2] = c1
        return True

Java

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

JavaScript

var isIsomorphic = function(s, t) {
    let m = new Map();
let n = new Map();
for(let i=0;i