Isomorphic String Mapping — Problem Statement & Solution Guide
Problem Description
Given two strings s and t, determine if there exists a one-to-one mapping between the characters of s and t. The mapping is valid if every character in s maps to a unique character in t and vice versa.
Examples
Input
{'s': 'egg', 't': 'add'}Output
false
Explanation: Step-by-step: 1. Create a dictionary to store the mapping of characters from s to t. 2. Iterate over the characters in s. 3. For each character in s, check if it's already in the dictionary. If it is, return false because a character in s maps to a character in t that is already mapped to another character in s. 4. If the character is not in the dictionary, add it to the dictionary with its corresponding character in t. 5. After iterating over all characters in s, check if all characters in t are in the dictionary. If not, return false because there are characters in t that are not mapped to any character in s. 6. If all characters in t are in the dictionary, return true because a one-to-one mapping exists between the characters of s and t.
Input
{'s': 'foo', 't': 'bar'}Output
false
Explanation: Step-by-step: 1. Create a dictionary to store the mapping of characters from s to t. 2. Iterate over the characters in s. 3. For each character in s, check if it's already in the dictionary. If it is, return false because a character in s maps to a character in t that is already mapped to another character in s. 4. If the character is not in the dictionary, add it to the dictionary with its corresponding character in t. 5. After iterating over all characters in s, check if all characters in t are in the dictionary. If not, return false because there are characters in t that are not mapped to any character in s. 6. If all characters in t are in the dictionary, return true because a one-to-one mapping exists between the characters of s and t.
Constraints
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
Optimal Approach & Strategy
Use two arrays of size 256 for mapping s->t and t->s. If mismatch found, return false. Time O(N), Space O(1).
Brute Force Approach
Replace characters and compare. Time O(N^2).
Verified Code Solutions
function isIsomorphic(s, t) { if (!s.length || !t.length) return true; let sToT = new Map(); let tToS = new Map(); for (let i = 0; i < s.length; i++) { if (sToT.has(s[i]) && sToT.get(s[i]) !== t[i]) return false; if (tToS.has(t[i]) && tToS.get(t[i]) !== s[i]) return false; if (!sToT.has(s[i]) && !tToS.has(t[i])) { sToT.set(s[i], t[i]); tToS.set(t[i], s[i]); } } return sToT.size === s.length; }class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
Map<Character, Character> charMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (charMap.containsKey(s.charAt(i)) && charMap.get(s.charAt(i)) != t.charAt(i)) {
return false;
} else if (!charMap.containsKey(s.charAt(i)) && charMap.containsValue(t.charAt(i))) {
return false;
} else {
charMap.put(s.charAt(i), t.charAt(i));
}
}
return charMap.size() == new HashSet<>(t.chars().boxed().collect(Collectors.toList())).size();
}
}def isomorphic_string_mapping(s, t):
if not s or not t:
return False
char_map = {}
for i in range(len(s)):
if s[i] in char_map and char_map[s[i]] != t[i]:
return False
elif s[i] not in char_map and t[i] in char_map.values():
return False
else:
char_map[s[i]] = t[i]
return len(char_map) == len(set(t))function isIsomorphic(s, t) { if (!s.length || !t.length) return true; let sToT = new Map(); let tToS = new Map(); for (let i = 0; i < s.length; i++) { if (sToT.has(s[i]) && sToT.get(s[i]) !== t[i]) return false; if (tToS.has(t[i]) && tToS.get(t[i]) !== s[i]) return false; if (!sToT.has(s[i]) && !tToS.has(t[i])) { sToT.set(s[i], t[i]); tToS.set(t[i], s[i]); } } return sToT.size === s.length; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.