Dare2Solve
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.
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.
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
.
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.
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.
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)
.
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.class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s.length() != t.length()) return false;
unordered_map<char, char> 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;
}
};
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
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Character> mapST = new HashMap<>();
Map<Character, Character> 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;
}
}
var isIsomorphic = function(s, t) {
let m = new Map();
let n = new Map();
for(let i=0;i<s.length;i++) {
m.set(s[i], t[i]);
}
for(let i=0;i<t.length;i++) {
n.set(t[i], s[i]);
}
for(let i=0;i<s.length;i++) {
if(m.get(s[i])!==t[i] || n.get(t[i])!==s[i]){
return false;
}
}
return true;
};