🎨Now live: Try our Free AI Image Generation Feature

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
- Length Check:
First, check if the lengths of
s
andt
are different. If they are, returnfalse
as strings of different lengths cannot be isomorphic. - Mapping Creation:
Use two dictionaries to create mappings from characters in
s
to characters int
and from characters int
to characters ins
. - Iterate and Map:
Iterate through each character pair
(c1, c2)
froms
andt
. - Check if there is an existing mapping forc1
in thes
tot
dictionary and forc2
in thet
tos
dictionary. - If there is a conflict in the mapping, returnfalse
. - Otherwise, create the mappings in both dictionaries. - 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
andt
takesO(n)
time, wheren
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