Two strings s and t are isomorphic if the characters in s can be replaced to get t, maintaining a one-to-one mapping between the characters. No two characters may map to the same character but a character may map to itself.
Steps
- Initialize two maps: one from
stotand the other fromttos. - Traverse both strings simultaneously.
- If a mapping doesn’t exist in either direction, create it.
- If the mapping exists but doesn’t match the current characters, return
false. - If the loop completes without conflicts, return
true.
Dry Run
Input: s = "egg", t = "add"
- e → a → map e → a, a → e
- g → d → map g → d, d → g
- g → d → maps exist and match → OK
- All checks passed → return
true
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the strings
- Space Complexity: O(1), as the mappings are bounded by character set size
var isIsomorphic = function(s, t) {
let mapSToT = {};
let mapTToS = {};
for (let i = 0; i < s.length; i++) {
if (!mapSToT[s[i]] && !mapTToS[t[i]]) {
mapSToT[s[i]] = t[i];
mapTToS[t[i]] = s[i];
} else if (mapTToS[t[i]] !== s[i] || mapSToT[s[i]] !== t[i]) {
return false;
}
}
return true;
};
#include <iostream>
#include <unordered_map>
using namespace std;
bool isIsomorphic(string s, string t) {
unordered_map<char, char> mapST, mapTS;
for (int i = 0; i < s.length(); i++) {
char cs = s[i], ct = t[i];
if (mapST.count(cs) == 0 && mapTS.count(ct) == 0) {
mapST[cs] = ct;
mapTS[ct] = cs;
} else {
if (mapST[cs] != ct || mapTS[ct] != cs)
return false;
}
}
return true;
}
#include <stdio.h>
#include <string.h>
int isIsomorphic(char* s, char* t) {
int mapST[256] = {0};
int mapTS[256] = {0};
for (int i = 0; s[i]; i++) {
if (mapST[(unsigned char)s[i]] == 0 && mapTS[(unsigned char)t[i]] == 0) {
mapST[(unsigned char)s[i]] = t[i];
mapTS[(unsigned char)t[i]] = s[i];
} else {
if (mapST[(unsigned char)s[i]] != t[i] || mapTS[(unsigned char)t[i]] != s[i])
return 0;
}
}
return 1;
}
import java.util.HashMap;
public class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> mapST = new HashMap<>();
HashMap<Character, Character> mapTS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char cs = s.charAt(i);
char ct = t.charAt(i);
if (!mapST.containsKey(cs) && !mapTS.containsKey(ct)) {
mapST.put(cs, ct);
mapTS.put(ct, cs);
} else {
if (!ct.equals(mapST.get(cs)) || !cs.equals(mapTS.get(ct)))
return false;
}
}
return true;
}
}
def isIsomorphic(s: str, t: str) -> bool:
map_s_t = {}
map_t_s = {}
for cs, ct in zip(s, t):
if cs not in map_s_t and ct not in map_t_s:
map_s_t[cs] = ct
map_t_s[ct] = cs
elif map_s_t.get(cs) != ct or map_t_s.get(ct) != cs:
return False
return True
